基于蟻群算法的無線傳感器網(wǎng)絡改進CTP路由協(xié)議

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

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

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

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

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

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

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

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

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

1.2 改進后的蟻群算法仿真

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

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

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

從圖1中可以看出，改進蟻群算法得到的網(wǎng)絡模型節(jié)點分布均勻，過遠的傳感器節(jié)點之間不會形成直接的傳輸路徑，接近現(xiàn)實中的網(wǎng)絡拓撲結構。將節(jié)點1設為數(shù)據(jù)采集節(jié)點，節(jié)點20設為目的節(jié)點，算法迭代次數(shù)為20次，每次出動螞蟻個數(shù)為100只螞蟻，信息素濃度重要參數(shù)α＝0.4，時間延遲重要參數(shù)β＝0.4，鏈路質量重要參數(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中的信息素濃度、時間延遲和鏈路質量在算法迭代到15次時收斂，說明改進后的算法是合理可行的。

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

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

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

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

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

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

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

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

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

圖5 ACA-CTP路由信息包

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

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

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

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

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

2.1.3 轉發(fā)引擎的改進 轉發(fā)引擎將更新后的路由表中的3個QoS參數(shù)代入公式（1）中，計算當前節(jié)點的各下一跳鄰居節(jié)點的路徑轉移概率，選取最大轉移概率鄰居節(jié)點作為當前節(jié)點的父節(jié)點，將ACA-CTP協(xié)議的數(shù)據(jù)包沿著最優(yōu)路徑傳輸至目標節(jié)點。同時，為了避免因信息素累積而使節(jié)點負載過大和轉發(fā)引擎陷入局部最優(yōu)路徑，信息素根據(jù)信息素更新機制進行揮發(fā)，經(jīng)過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)絡的拓撲結構，TOSSIM仿真才能模擬網(wǎng)絡行為，故仿真剛啟動時，節(jié)點之間不能互相通信。提取農(nóng)業(yè)大棚環(huán)境的網(wǎng)絡參數(shù)，使用TOSSIM自帶的Java工具根據(jù)對數(shù)正態(tài)陰影路徑損耗模型產(chǎn)生網(wǎng)絡拓撲，需要的配置文件中的網(wǎng)絡參數(shù)如表1所示。

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

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

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

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

3.2 仿真結果分析

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

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

圖7 中，〈8〉號節(jié)點的轉發(fā)引擎（CtpForwardingEngineP）觸發(fā)發(fā)送任務（sendTask）—轉發(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ù)包進入轉發(fā)隊列（Queue:size is 1），廣 播 路 由 幀 （head＜ － ＜ －tail）；最后仿真完成（Completed simulation）。圖7可以清楚地反映ACA-CTP路由協(xié)議下數(shù)據(jù)包的傳輸流程，但不能直觀反映路由協(xié)議的性能。因此，本文收集仿真過程中各節(jié)點的仿真信息，繪制ACACTP路由協(xié)議網(wǎng)絡拓撲圖（圖8）。

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

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

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

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

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

由上述拓撲圖可知，3種路由協(xié)議生成的網(wǎng)絡拓撲均為樹形網(wǎng)絡。比較3個不同的網(wǎng)絡拓撲可以看出，ACA-CTP路由協(xié)議生成的網(wǎng)絡拓撲中第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)絡拓撲中，24號節(jié)點的負載為11，8號節(jié)點的負載為7，9號節(jié)點的負載為2，25號節(jié)點的負載為5。AODV路由協(xié)議生成的網(wǎng)絡拓撲中，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)絡負載均衡度（Network-Load Balance Degree，NLBD）作為衡量網(wǎng)絡負載均衡性的標準。負載均衡度的值越小，說明該樹形網(wǎng)絡的節(jié)點負載越均衡，如果負載均衡度的值為零，說明該樹形網(wǎng)絡是一顆均衡匯聚樹。負載均衡度

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

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

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

由表4可知，ACA-CTP路由協(xié)議的網(wǎng)絡負載均衡度最小，其均衡節(jié)點負載的能力最強；AODV路由協(xié)議的網(wǎng)絡負載均衡度次之，其均衡節(jié)點負載的能力適中；CTP路由協(xié)議的網(wǎng)絡負載均衡度最大，其均衡節(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é)議更快，從而能在較短時間內搜索到滿足QoS約束要求的最優(yōu)路徑。但是隨著路由協(xié)議運行時間的推移，網(wǎng)絡的拓撲結構逐漸穩(wěn)定，其傳輸時延也趨于穩(wěn)定，3種路由協(xié)議之間傳輸時延的差異逐漸縮小。

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

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

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

4 結束語

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

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

［2］ 劉擁明，蔣新華，年曉紅.無線傳感器網(wǎng)絡擁塞控制研究［J］.計算機應用研究，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é)議設計［J］.計算機應用研究，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］.清華大學學報（自然科學版），2003，43（01）:1-4.

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

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

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

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

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