基于蟻群算法的無線傳感器網絡改進CTP路由協議

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

（1湖北工業大學機械工程學院，湖北 武漢430068；2湖北工業大學農業機械工程研究設計院，湖北 武漢430068）

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

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

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

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

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

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

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

1.2 改進后的蟻群算法仿真

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

運行算法后生成的網絡拓撲如圖1所示。

圖1 網絡拓撲圖

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

運行算法后生成的最優路徑如圖2所示。

圖2 最優路徑圖

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

圖3 QoS度量參數收斂圖

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

2 ACA-CTP路由協議

2.1 ACA-CTP路由協議的實現

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

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

圖4 ACA-CTP路由協議框架圖

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

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

圖5 ACA-CTP路由信息包

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

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

Timedelay為當前節點到源節點的數據傳輸時延，占8個位；

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

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

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

圖6 ACA-CTP路由協議流程圖

3 ACA-CTP路由協議的仿真

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

3.1 仿真環境的搭建

本文選取某農科院農業大棚環境作為仿真環境，建立TOSSIM仿真模型。由于只有配置好網絡的拓撲結構，TOSSIM仿真才能模擬網絡行為，故仿真剛啟動時，節點之間不能互相通信。提取農業大棚環境的網絡參數，使用TOSSIM自帶的Java工具根據對數正態陰影路徑損耗模型產生網絡拓撲，需要的配置文件中的網絡參數如表1所示。

表1 網絡拓撲參數配置表

配置文件中的節點坐標是根據農業大棚環境現場節點部署的實際位置測定的，13個節點的坐標分布如表2所示。

表2 實驗現場節點坐標分布表

運行Java工具，生成兩個文件“linkgain.out”和“topology.out”。其中，“linkgain.out”文件包含了網絡中任意兩個節點之間的鏈路增益和噪聲；而“topology.out”文件包含了仿真環境中節點的坐標分布。

3.2 仿真結果分析

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

圖7 ACA-CTP路由協議仿真圖

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

圖8 ACA-CTP協議網絡拓撲圖

分別運行原始CTP路由協議和AODV路由協議，得到網絡拓撲圖分別如圖9和圖10所示。

圖9 CTP協議網絡拓撲圖

圖10 AODV協議網絡拓撲圖

其中，圖10為在某農科院農業大棚現場測試農業大棚無線監測系統時，上位機監控軟件直接繪出的網絡拓撲圖。在網絡拓撲中，黑色節點為匯聚節點，白色節點為路由節點，灰節點為終端節點。

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

表3 三種不同協議下節點負載表

為了比較3種路由協議平衡節點負載性能的優劣，引入網絡負載均衡度（Network-Load Balance Degree，NLBD）作為衡量網絡負載均衡性的標準。負載均衡度的值越小，說明該樹形網絡的節點負載越均衡，如果負載均衡度的值為零，說明該樹形網絡是一顆均衡匯聚樹。負載均衡度

式中:VNLBD為樹形網絡的負載均衡度的值；Li為節點負載的值；L為節點負載的均值；n為樹形網絡中路由節點個數。

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

表4 三種不同路由協議的網絡負載均衡度表

由表4可知，ACA-CTP路由協議的網絡負載均衡度最小，其均衡節點負載的能力最強；AODV路由協議的網絡負載均衡度次之，其均衡節點負載的能力適中；CTP路由協議的網絡負載均衡度最大，其均衡節點負載的能力最差。

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

圖11 三種路由協議傳輸時延的比較

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

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

圖12 三種路由協議網絡收包率比較

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

4 結束語

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

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

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

［3］ Gnawali O，Fonseca 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路由協議設計［J］.計算機應用研究，2013，30（02）:541-543.

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

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

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

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

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

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

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

［12］黃森茂.無線傳感器網絡能量優化策略研究及時間同步算法實現［D］.武漢:湖北工業大學，2013.