陳 昊，楊光友，，馬志艷，，鄭 拓，全 睿

（1湖北工業(yè)大學(xué)機械工程學(xué)院，湖北 武漢430068；2湖北工業(yè)大學(xué)農(nóng)業(yè)機械工程研究設(shè)計院，湖北 武漢430068）

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）節(jié)點具有體積小、能耗低等優(yōu)點，但同時又有能量有限、計算能力有限、帶寬有限和易受干擾等缺點［1－2］。因此，設(shè)計節(jié)能高效的路由協(xié)議是 WSN的主要研究內(nèi)容之一［3］。路由算法的路徑選擇機制的優(yōu)劣和執(zhí)行效率的高低將直接決定傳感器節(jié)點負載均衡程度、采集數(shù)據(jù)和收發(fā)數(shù)據(jù)的速率，從而影響整個網(wǎng)絡(luò)的能耗和時延。網(wǎng)絡(luò)拓撲中路由節(jié)點的負載過重會導(dǎo)致節(jié)點過度能耗而死亡，影響整個網(wǎng)絡(luò)的性能和生命周期。同時，過載節(jié)點傳輸隊列過長，影響數(shù)據(jù)的實時傳輸［4］。針對上述缺點，目前國內(nèi)外已有學(xué)者對路由協(xié)議改進優(yōu)化?；诰鈪R聚樹的路由算法LB-CTP定義節(jié)點均衡度，引入規(guī)避繁忙節(jié)點接入機制，在路由更新中，相應(yīng)節(jié)點以LB-CTP路由算法選擇父節(jié)點接入網(wǎng)絡(luò)，分擔(dān)繁忙節(jié)點負擔(dān)，有效均衡了網(wǎng)絡(luò)負載［5］。文獻［6］在TinyOS系統(tǒng)中實現(xiàn)了基于蟻群算法的路由協(xié)議，該協(xié)議采用多跳的通信方式，能夠在降低丟包率和傳輸時延的同時平衡節(jié)點的能量消耗，延長了網(wǎng)絡(luò)的存活時間。上述路由協(xié)議只是單一地優(yōu)化節(jié)點負載，沒有同時考慮網(wǎng)絡(luò)時延和節(jié)點間鏈路質(zhì)量，應(yīng)用到實際中仍存在一些缺陷。

本文提出了一種結(jié)合蟻群算法和CTP路由協(xié)議的路由算法——蟻群匯聚樹算法（Ant Colony Algorithm Collection Tree Protocol，ACA-CTP），并在TinyOS系統(tǒng)中運用NesC語言實現(xiàn)了該算法。算法在原有CTP路由協(xié)議的基礎(chǔ)上，將蟻群算法的控制機制加入到CTP路由協(xié)議中，通過調(diào)整信息素濃度、節(jié)點間鏈路質(zhì)量和數(shù)據(jù)包時間延遲三者之間的關(guān)系來指引路由包進行路徑搜索，算法的自適應(yīng)性好，全局搜索能力和快速收斂性兩者之間較為均衡。最后通過TOSSIM仿真，比較了CTP路由協(xié)議、AODV路由協(xié)議和ACA-CTP路由協(xié)議的性能。

1 ACA-CTP路由協(xié)議中的蟻群算法控制機制

1.1 改進后的蟻群算法控制機制

本文以節(jié)點間鏈路質(zhì)量qij和傳輸時延tij構(gòu)建啟發(fā)式因子ηij，作為QoS網(wǎng)絡(luò)路由對路徑優(yōu)劣的評價參數(shù)［7－8］；同時考慮到傳感器節(jié)點的計算能力有限，選擇概率函數(shù)從乘冪公式改為乘法公式，提高算法的計算效率。改進后的蟻群算法概率選擇公式:

其中，α、β和γ分別是信息素濃度τij、時間延遲tij和鏈路質(zhì)量qij的可調(diào)權(quán)重。螞蟻的路徑選擇傾向可以通過選擇不同的α、β和γ值來調(diào)節(jié)，時延越短，鏈路質(zhì)量越好，啟發(fā)式因子越大，螞蟻選擇該路徑的概率就越大。同時，這3個參數(shù)對蟻群算法的全局尋優(yōu)性能和快速收斂性能的影響和作用是相互配合，密切相關(guān)的，只有正確選擇三者之間的搭配關(guān)系，才能避免在搜索過程中出現(xiàn)過早停滯或陷入局部最優(yōu)等情況的發(fā)生。因此，令α、β和γ三者之間的關(guān)系如下:

改進后的蟻群算法的信息素更新機制同基本蟻群算法相同。通過合理的設(shè)置信息素更新機制中的有關(guān)參數(shù)和α、β、γ3個參數(shù)，就可以實現(xiàn)算法收斂速度與全局尋優(yōu)性能之間的平衡［9－10］，使網(wǎng)絡(luò)負載達到平衡，延長網(wǎng)絡(luò)生命周期。

1.2 改進后的蟻群算法仿真

為了驗證改進蟻群算法的可行性和普通性，建立隨機網(wǎng)絡(luò)拓撲結(jié)構(gòu)，運用Matlab仿真工具對其進行仿真研究。仿真環(huán)境是在100m×100m的區(qū)域中隨機生成200個節(jié)點，用K均值聚類算法對這些節(jié)點進行聚類，最終得到20個中心點，這20個中心點即為所需傳感器節(jié)點，節(jié)點通信半徑為50m。隨機網(wǎng)絡(luò)中節(jié)點的時延、鏈路質(zhì)量和信息素濃度隨機產(chǎn)生，其中，鏈路質(zhì)量qij取0～1的隨機數(shù)，時間延遲tij取0～25的隨機數(shù)，信息素濃度τij取0～10的隨機數(shù)。

運行算法后生成的網(wǎng)絡(luò)拓撲如圖1所示。

圖1 網(wǎng)絡(luò)拓撲圖

從圖1中可以看出，改進蟻群算法得到的網(wǎng)絡(luò)模型節(jié)點分布均勻，過遠的傳感器節(jié)點之間不會形成直接的傳輸路徑，接近現(xiàn)實中的網(wǎng)絡(luò)拓撲結(jié)構(gòu)。將節(jié)點1設(shè)為數(shù)據(jù)采集節(jié)點，節(jié)點20設(shè)為目的節(jié)點，算法迭代次數(shù)為20次，每次出動螞蟻個數(shù)為100只螞蟻，信息素濃度重要參數(shù)α＝0.4，時間延遲重要參數(shù)β＝0.4，鏈路質(zhì)量重要參數(shù)γ＝0.2，信息素蒸發(fā)系數(shù)ρ＝0.8，信息素增強系數(shù)w＝30。

運行算法后生成的最優(yōu)路徑如圖2所示。

圖2 最優(yōu)路徑圖

如圖2中所示，運行改進蟻群算法后得到的最優(yōu)傳輸路徑為1－9－15－16－20，并且圖3中的信息素濃度、時間延遲和鏈路質(zhì)量在算法迭代到15次時收斂，說明改進后的算法是合理可行的。

圖3 QoS度量參數(shù)收斂圖

通過仿真測試，證明ACA-CTP算法中的蟻群算法控制機制能根據(jù)信息素濃度、時間延遲和鏈路質(zhì)量自動選擇最優(yōu)路徑，自適應(yīng)地選擇和維護節(jié)點路由，為ACA-CTP路由協(xié)議的實現(xiàn)奠定了理論基礎(chǔ)。

2 ACA-CTP路由協(xié)議

2.1 ACA-CTP路由協(xié)議的實現(xiàn)

ACA-CTP協(xié)議在CTP協(xié)議的基礎(chǔ)之上，以鏈路質(zhì)量、時間延遲和信息素濃度等3個QoS參數(shù)代替CTP協(xié)議中的單一鏈路質(zhì)量參數(shù)作為新的路由選擇度量，引入蟻群算法控制機制，利用蟻群算法的路徑尋優(yōu)和快速收斂特性選擇數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑［11］。

ACA-CTP路由協(xié)議的改進如圖4所示。

圖4 ACA-CTP路由協(xié)議框架圖

2.1.1 鏈路質(zhì)量估計器的改進 如圖4所示，鏈路質(zhì)量估計器引入時間延遲這一新的度量作為評價網(wǎng)絡(luò)狀況的參數(shù)，同時為了獲得節(jié)點間傳輸數(shù)據(jù)包的時間延遲估計，引入FTSP時間同步算法［12］。在TinyOS操作系統(tǒng)中，可以直接使用定時器組件TimeSyncC提供的接口來實現(xiàn)FTSP算法。

2.1.2 路由引擎的改進 新的路由表在原CTP協(xié)議的路由表的基礎(chǔ)上增加了信息素濃度、數(shù)據(jù)傳輸時延和節(jié)點間鏈路質(zhì)量等3個表項，隨著鏈路質(zhì)量估計器實時地計算傳輸時延和鏈路質(zhì)量而周期性地更新路由表，路由引擎將路由表中的信息傳輸至轉(zhuǎn)發(fā)引擎。ACA-CTP協(xié)議的路由信息包格式如圖5所示。

圖5 ACA-CTP路由信息包

ACA-CTP路由信息包中各個字段的作用如下:P為允許路由位，占1個位，P位允許節(jié)點從其他節(jié)點請求路由信息；C為擁塞標(biāo)識位，占1個位，如果節(jié)點丟棄了一個路由幀，則必須將下一個傳輸路由幀的C位置位；Reserved為保留位，占6個位；Parent為父節(jié)點ID，占8個位；Current為當(dāng)前節(jié)點ID，占8個位，

Quality為當(dāng)前節(jié)點到源節(jié)點的鏈路質(zhì)量，占8個位，

Timedelay為當(dāng)前節(jié)點到源節(jié)點的數(shù)據(jù)傳輸時延，占8個位；

Pheromone為當(dāng)前節(jié)點的初始信息素濃度，占8個位。

在ACA-CTP路由協(xié)議的實現(xiàn)中，路由引擎調(diào)用UpdateRouteTask函數(shù)來更新路由表中的信息素濃度、傳輸時延和鏈路質(zhì)量等表項，轉(zhuǎn)發(fā)引擎就能動態(tài)選擇當(dāng)前節(jié)點的下一跳節(jié)點，保證數(shù)據(jù)實時準(zhǔn)確地傳輸至目的節(jié)點。

2.1.3 轉(zhuǎn)發(fā)引擎的改進 轉(zhuǎn)發(fā)引擎將更新后的路由表中的3個QoS參數(shù)代入公式（1）中，計算當(dāng)前節(jié)點的各下一跳鄰居節(jié)點的路徑轉(zhuǎn)移概率，選取最大轉(zhuǎn)移概率鄰居節(jié)點作為當(dāng)前節(jié)點的父節(jié)點，將ACA-CTP協(xié)議的數(shù)據(jù)包沿著最優(yōu)路徑傳輸至目標(biāo)節(jié)點。同時，為了避免因信息素累積而使節(jié)點負載過大和轉(zhuǎn)發(fā)引擎陷入局部最優(yōu)路徑，信息素根據(jù)信息素更新機制進行揮發(fā)，經(jīng)過N次迭代后，信息素濃度降低，確保轉(zhuǎn)發(fā)引擎選取路徑是最優(yōu)路徑。ACA-CTP路由算法流程圖如圖6所示。

圖6 ACA-CTP路由協(xié)議流程圖

3 ACA-CTP路由協(xié)議的仿真

在TinyOS操作系統(tǒng)中使用TOSSIM仿真器仿真ACA-CTP路由協(xié)議。不同于傳統(tǒng)的仿真，TOSSIM仿真器通過對實際的TinyOS程序進行編譯，建立更加真實的仿真環(huán)境，對ACA-CTP路由協(xié)議的性能做更加真實的分析。

3.1 仿真環(huán)境的搭建

本文選取某農(nóng)科院農(nóng)業(yè)大棚環(huán)境作為仿真環(huán)境，建立TOSSIM仿真模型。由于只有配置好網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，TOSSIM仿真才能模擬網(wǎng)絡(luò)行為，故仿真剛啟動時，節(jié)點之間不能互相通信。提取農(nóng)業(yè)大棚環(huán)境的網(wǎng)絡(luò)參數(shù)，使用TOSSIM自帶的Java工具根據(jù)對數(shù)正態(tài)陰影路徑損耗模型產(chǎn)生網(wǎng)絡(luò)拓撲，需要的配置文件中的網(wǎng)絡(luò)參數(shù)如表1所示。

表1 網(wǎng)絡(luò)拓撲參數(shù)配置表

配置文件中的節(jié)點坐標(biāo)是根據(jù)農(nóng)業(yè)大棚環(huán)境現(xiàn)場節(jié)點部署的實際位置測定的，13個節(jié)點的坐標(biāo)分布如表2所示。

表2 實驗現(xiàn)場節(jié)點坐標(biāo)分布表

運行Java工具，生成兩個文件“l(fā)inkgain.out”和“topology.out”。其中，“l(fā)inkgain.out”文件包含了網(wǎng)絡(luò)中任意兩個節(jié)點之間的鏈路增益和噪聲；而“topology.out”文件包含了仿真環(huán)境中節(jié)點的坐標(biāo)分布。

3.2 仿真結(jié)果分析

仿真環(huán)境配置完成后，在TinyOS協(xié)議棧的應(yīng)用層編寫ACA-CTP路由協(xié)議的應(yīng)用程序，運行TOSSIM仿真器，仿真結(jié)果如圖7所示。

圖7 ACA-CTP路由協(xié)議仿真圖

圖7 中，〈8〉號節(jié)點的轉(zhuǎn)發(fā)引擎（CtpForwardingEngineP）觸發(fā)發(fā)送任務(wù)（sendTask）—轉(zhuǎn)發(fā)（Trying to send a packet）發(fā)送隊列（Queue）中的數(shù)據(jù)包，此時發(fā)送隊列中只有一個數(shù)據(jù)包（Queue size is 1），節(jié)點不處于擁塞狀態(tài)；但是沒有發(fā)現(xiàn)合理的路由路徑（no route，don′t send），再次發(fā)起路由請求（start retry timer）；發(fā)現(xiàn)路由路徑，發(fā)送數(shù)據(jù)包，發(fā)送隊列為空（Queue:size is 0）；然后收到一個數(shù)據(jù)包（head＜－［負載］＜－tail），數(shù)據(jù)包進入轉(zhuǎn)發(fā)隊列（Queue:size is 1），廣 播 路 由 幀 （head＜ － ＜ －tail）；最后仿真完成（Completed simulation）。圖7可以清楚地反映ACA-CTP路由協(xié)議下數(shù)據(jù)包的傳輸流程，但不能直觀反映路由協(xié)議的性能。因此，本文收集仿真過程中各節(jié)點的仿真信息，繪制ACACTP路由協(xié)議網(wǎng)絡(luò)拓撲圖（圖8）。

圖8 ACA-CTP協(xié)議網(wǎng)絡(luò)拓撲圖

分別運行原始CTP路由協(xié)議和AODV路由協(xié)議，得到網(wǎng)絡(luò)拓撲圖分別如圖9和圖10所示。

圖9 CTP協(xié)議網(wǎng)絡(luò)拓撲圖

圖10 AODV協(xié)議網(wǎng)絡(luò)拓撲圖

其中，圖10為在某農(nóng)科院農(nóng)業(yè)大棚現(xiàn)場測試農(nóng)業(yè)大棚無線監(jiān)測系統(tǒng)時，上位機監(jiān)控軟件直接繪出的網(wǎng)絡(luò)拓撲圖。在網(wǎng)絡(luò)拓撲中，黑色節(jié)點為匯聚節(jié)點，白色節(jié)點為路由節(jié)點，灰節(jié)點為終端節(jié)點。

由上述拓撲圖可知，3種路由協(xié)議生成的網(wǎng)絡(luò)拓撲均為樹形網(wǎng)絡(luò)。比較3個不同的網(wǎng)絡(luò)拓撲可以看出，ACA-CTP路由協(xié)議生成的網(wǎng)絡(luò)拓撲中第1層節(jié)點均為路由節(jié)點，其子節(jié)點數(shù)目相同，每個路由節(jié)點都擁有2個直屬子節(jié)點；第2層節(jié)點中的2個路由節(jié)點均有3個終端節(jié)點作為直屬子節(jié)點，因此，9號節(jié)點和25號節(jié)點的負載均為3，24號節(jié)點的負載為8，而8號節(jié)點的負載為2。同理，CTP路由協(xié)議生成的網(wǎng)絡(luò)拓撲中，24號節(jié)點的負載為11，8號節(jié)點的負載為7，9號節(jié)點的負載為2，25號節(jié)點的負載為5。AODV路由協(xié)議生成的網(wǎng)絡(luò)拓撲中，24號節(jié)點的負載為11，8號節(jié)點的負載為9，9號節(jié)點的負載為6，25號節(jié)點的負載為3。3種路由協(xié)議下節(jié)點負載如表3所示。

表3 三種不同協(xié)議下節(jié)點負載表

為了比較3種路由協(xié)議平衡節(jié)點負載性能的優(yōu)劣，引入網(wǎng)絡(luò)負載均衡度（Network-Load Balance Degree，NLBD）作為衡量網(wǎng)絡(luò)負載均衡性的標(biāo)準(zhǔn)。負載均衡度的值越小，說明該樹形網(wǎng)絡(luò)的節(jié)點負載越均衡，如果負載均衡度的值為零，說明該樹形網(wǎng)絡(luò)是一顆均衡匯聚樹。負載均衡度

式中:VNLBD為樹形網(wǎng)絡(luò)的負載均衡度的值；Li為節(jié)點負載的值；L為節(jié)點負載的均值；n為樹形網(wǎng)絡(luò)中路由節(jié)點個數(shù)。

分別用式（3）計算3種路由協(xié)議生成網(wǎng)絡(luò)拓撲的網(wǎng)絡(luò)負載均衡度，得到的結(jié)果如表4所示。

表4 三種不同路由協(xié)議的網(wǎng)絡(luò)負載均衡度表

由表4可知，ACA-CTP路由協(xié)議的網(wǎng)絡(luò)負載均衡度最小，其均衡節(jié)點負載的能力最強；AODV路由協(xié)議的網(wǎng)絡(luò)負載均衡度次之，其均衡節(jié)點負載的能力適中；CTP路由協(xié)議的網(wǎng)絡(luò)負載均衡度最大，其均衡節(jié)點負載的能力最差。

ACA-CTP路由協(xié)議生成一顆4層匯聚樹，CTP路由協(xié)議生成一顆5層匯聚樹，而AODV路由協(xié)議生成一顆6層匯聚樹，終端節(jié)點向匯聚節(jié)點傳輸數(shù)據(jù)時所經(jīng)過的層數(shù)越多，其累計的傳輸時延也越大。三種路由算法的傳輸時延變化趨勢如圖11所示。

圖11 三種路由協(xié)議傳輸時延的比較

圖11 說明ACA-CTP路由協(xié)議相比其他兩種協(xié)議有更好的實時性，這是由于引入了蟻群算法機制，ACA-CTP路由協(xié)議的收斂速度比其他兩種協(xié)議更快，從而能在較短時間內(nèi)搜索到滿足QoS約束要求的最優(yōu)路徑。但是隨著路由協(xié)議運行時間的推移，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)逐漸穩(wěn)定，其傳輸時延也趨于穩(wěn)定，3種路由協(xié)議之間傳輸時延的差異逐漸縮小。

收包率是衡量節(jié)點間鏈路質(zhì)量的重要指標(biāo)，圖12顯示了3種路由協(xié)議生成網(wǎng)絡(luò)中收包率的變化情況。

圖12 三種路由協(xié)議網(wǎng)絡(luò)收包率比較

圖12 反映出隨著協(xié)議運行時間的逐漸增加，網(wǎng)絡(luò)拓撲結(jié)構(gòu)趨于穩(wěn)定，網(wǎng)絡(luò)收包率也逐漸升高，ACA-CTP協(xié)議下網(wǎng)絡(luò)的收包率略高于其他兩種協(xié)議的收包率，但三者之間的差距不大。因此，鏈路質(zhì)量這一QoS約束在信息素濃度、傳輸時延和鏈路質(zhì)量這3個參量中所占權(quán)重較小，不應(yīng)作為選擇最優(yōu)路徑時的決定性因素。

4 結(jié)束語

本文提出了基于蟻群算法和CTP路由協(xié)議相結(jié)合的路由協(xié)議ACA-CTP，并在TinyOS系統(tǒng)的網(wǎng)絡(luò)層和應(yīng)用層實現(xiàn)了該路由協(xié)議，通過TinyOS系統(tǒng)自帶的TOSSIM仿真器驗證了ACA-CTP路由協(xié)議能夠較好地均衡網(wǎng)絡(luò)中節(jié)點的負載，減少數(shù)據(jù)包的傳輸時延和改善節(jié)點間鏈路質(zhì)量，為提高農(nóng)業(yè)大棚監(jiān)測系統(tǒng)的多跳數(shù)據(jù)傳輸性能奠定了基礎(chǔ)。但是，本文只對ACA-CTP路由協(xié)議進行了仿真，該協(xié)議在實際應(yīng)用中的性能還有待驗證。

［1］ 余小華，黃燦輝.一種基于蟻群優(yōu)化的 WSN擁塞控制算法［J］.計算機應(yīng)用研究，2012，29（04）:1 525-1 528.

［2］ 劉擁明，蔣新華，年曉紅.無線傳感器網(wǎng)絡(luò)擁塞控制研究［J］.計算機應(yīng)用研究，2008，25（02）:565-568.

［3］ Gnawali O，F(xiàn)onseca R，Jamieson K.Collection tree protocol［C］//Proc.Of the 7th ACM Conference on Embedded Networked Sensor Systems.Berkeley，USA:ACM Press，2009.

［4］ 魯天龍，盧俊嶺，王小明，等.TinyOS2，x下基于蟻群算法的 WSNS路由協(xié)議設(shè)計［J］.計算機應(yīng)用研究，2013，30（02）:541-543.

［5］ 趙晨旭，吳怡之，韓漢光.基于 WSN均衡匯聚樹的CTP路由算法改進［J］.計算機工程，2012，38（14）:62-65.

［6］ 王 鑫，徐 攀，楊慧中.基于蟻群算法的路由協(xié)議在TinyOS中的實現(xiàn)［J］.傳感器與微系統(tǒng)，2012，31（05）:40-43.

［7］ 林國輝，馬正新，王勇前，等.基于螞蟻算法的擁塞規(guī)避路由算法［J］.清華大學(xué)學(xué)報（自然科學(xué)版），2003，43（01）:1-4.

［8］ 楊新峰，劉克成.基于改進蟻群算法的 WSN路徑優(yōu)化［J］.計算機與現(xiàn)代化，2012（06）:102-105.

［9］ 劉瑞杰，胡小兵.基于動態(tài)調(diào)節(jié)信息素增量的蟻群算法［J］.計算機應(yīng)用研究，2012，29（01）:135-137.

［10］陳鳳超，李融林.基于路由代價的無線傳感器網(wǎng)絡(luò)蟻群路由算法［J］.華南理工大學(xué)學(xué)報（自然科學(xué)版），2011，39（05）:36-43.

［11］潘 浩，董齊芬，張貴軍，等.無線傳感器網(wǎng)絡(luò)操作系統(tǒng)TinyOS［M］.北京:清華大學(xué)出版社，2011:279-282.

［12］黃森茂.無線傳感器網(wǎng)絡(luò)能量優(yōu)化策略研究及時間同步算法實現(xiàn)［D］.武漢:湖北工業(yè)大學(xué)，2013.