無線傳感器網絡中定向擴散路由協議的研究

尹中康 孫恩巖 王傳云 譚明爵

摘 要：路由協議是無線傳感器網絡設計中的一項重要技術，文中提出一種高效、節能的路由協議。分析原始DD協議，對原始協議中由于節點的選擇策略導致網絡中存在能量消耗不均的問題進行改進，同時考慮改進后的協議中傳感器當前節點與下一跳節點間的距離以及下一跳節點的剩余能量，使得網絡的生命周期、網絡節點的剩余能量以及網絡節點的能量均方差得以提高。通過仿真得出，改進后的協議更適合于無線圖像傳感器網絡的數據傳輸，可延長整個傳感器網絡的生命周期。

關鍵詞：無線傳感器網絡；DD協議；螞蟻算法；網絡節點

中圖分類號：TP212 文獻標識碼：A 文章編號：2095-1302（2018）08-00-03

0 引 言

本文主要對現有的定向擴散協議[1-3]（Directed Diffusion，DD）進行改進并實現仿真，使其能適合于無線傳感器網絡。在改進的DD協議中同時考慮節點間的傳輸距離以及節點間的剩余能量，使得網絡中節點的剩余能量比較平均，從而避免原始協議中能量較小的節點因承擔通信距離較長的網絡數據傳輸任務而導致能量消耗過快最終提前“死亡”的現象，最終使得整個網絡的生命周期得到顯著提高，同時能耗也比較均衡。

1 定向擴散協議的概念過程分析

DD協議是一種基于查詢的路由方法，查詢命令由匯聚節點發出，傳感器向查詢節點報告采集到的數據。在DD協議中，協議的執行由興趣擴散過程、梯度建立過程及路徑加強過程組成，定向擴散路由協議的過程如圖1所示。興趣設計的目的是向全網絡中的節點發出信息，并表明匯聚節點想要的數據類型。興趣向網絡中的擴散采用泛洪方式，如圖1（a）所示。在興趣廣播完成后，源節點與匯聚節點之間的梯度就建立完畢，最后形成的梯度如圖1（b）所示。當網絡中的傳感器節點采集到相關匹配數據后，向所有感興趣的鄰近節點轉發該數據，若收到該數據的鄰近節點不是匯聚節點，則采用同樣的方式轉發該數據。因此匯聚節點會收到從不同路徑上傳送來的相同數據，在收到這些數據后，匯聚節點選擇一條最優路徑作為強化路徑，后續數據沿該路徑傳播，如圖1（c）所示。

2 利用蟻群算法模擬實現原始定向擴散路由協議

利用蟻群算法（Ant Colony Optimization，ACO）模擬實現傳感器網絡中尋找一條從源節點到匯聚節點的最短路徑[4-6]。假設算法中螞蟻的數量為m，整個無線傳感器網絡中傳感器節點的個數（即螞蟻覓食過程中路口的個數）為n。

2.1 算法中各個參數的初始化操作

算法中各個參數的初始化操作步驟如下：

（1）將m只螞蟻放到待搜索路徑的起始位置（即匯聚節點的位置），同時為每只螞蟻設置一個路徑禁忌表，用來標記每只螞蟻走過的路徑，避免下次尋找路徑時重復選擇走過的路。其初始化操作為將每只螞蟻的路徑搜索禁忌表tabuk（s）中的第一個元素tabuk（1）設置為當前起始位置。

（2）為所有路徑賦予信息素值τ（i，j）=C（C為常數）。

（3）為網絡中的匯聚節點和源節點賦予較大的能量初值，將其他節點視為普通節點，賦予較小的能量初值。

2.2 算法中路徑的選擇規則

在t時刻，螞蟻k在節點i位置選擇其鄰近節點j時的概率按照以下公式確定：

（1）

式中：Jk（i）代表下一個可以選擇的所有節點集合，即傳感節點中螞蟻k尚未經過的節點集合；ηij是按概率選擇下一跳時的啟發因子，其大小取決于兩節點間距離的倒數；α，β表示概率公式中信息素因子和啟發式因子相對重要程度的大小，并且在算法執行過程中其值保持不變。

2.3 算法中信息素的更新

在所有螞蟻完成一次路徑搜索后，對所有路徑上的信息素進行規則重置：

（2）

式中：Q為常系數；ρ為各條路徑上信息素的揮發速率，其值在

[0，1]之間；Δτij為路徑ij上信息素增加量；Δτkij為螞蟻k在路徑ij上留下的信息素；Lk表示螞蟻k所走過路徑的路程。為了找到從源節點到匯聚節點的最短路徑[7]，設置螞蟻搜索路徑的迭代次數iter，用來控制算法結束的終止條件。在算法中設置一個變量Route_best，大小為iter×n的二維數組，用來記錄各代路徑中最短路徑所經過的每個節點的順序。在算法中設置一個變量Length_best，其是大小為iter×1的一維數組，用來記錄各代路徑中最短路徑的長度。蟻群算法解決最短路徑流程如圖2所示。

2.4 能量消耗計算

假設網絡中有node_A和node_B兩個傳感器節點，它們之間的距離為d m，當節點node_A向節點node_B發送

k bit數據包時，節點node_A和node_B消耗的能量計算公式

如下[7]：

（3）

（4）

式中：ETX-elec（k）表示功率放大器消耗的能量；Eelec表示傳感器節點中無線發射電路的能量損耗。

由式（3）可以看出，當發送端節點發送數據時，發送節點消耗的能量由發射電路損耗與功率放大損耗兩部分能耗構成。當兩節點間的距離小于常數值d0時，功率放大采用自由空間模型；當兩節點間的距離大于常數值d0時，功率放大采用多路徑衰減模型。式（3）中的εfs與εamp分別表示這兩種模型所對應功率放大能量的大小。

3 對原始DD協議的改進

在原始定向擴散的基礎上，增加一個變量Eall（i），用來記錄傳感器網絡中節點i的初始能量；增加一個變量Erem（i），用來記錄網絡中節點i的剩余能量，其大小等于Eall（i）減去已經消耗的能量，具體計算步驟如下：

（1）計算節點間的距離：

（5）

（2）計算候選節點的剩余能量：

（6）

（3）綜合考慮節點間的距離以及剩余能量對選擇概率所占的權重，決定最終選擇的節點：

（7）

式中u是[0，1]之間的常數。

（4）當候選節點的相鄰節點間出現相同概率的節點時，在候選節點中隨機選擇其中一個節點作為下一跳。

（5）對信息素的更新與原始DD協議相同。

4 原始協議的仿真

仿真過程是將無線傳感器網絡模型抽象成為一個二維平面帶權的無向圖。在無向圖中，G=（V，A），其中，V=（V1，V2，…，Vn）代表無線傳感器網絡中的節點集合。在仿真過程中，對集合中的每個節點賦予一個能量初值。在節點集合中，V1代表匯聚節點，Vn代表源節點，其余節點代表網絡中的普通節點；A代表無向圖中所有邊的集合，對每一條邊都賦予一個權值，表示邊所連接的兩個節點間距離的大小。

在Matlab中產生一個18 m×25 m的二維平面區域，部署45個無線傳感器節點。節點之間有線相連表示兩節點可以進行數據通信；否則不能進行數據通信[8-9]。尋找最短路徑的模擬場景如圖3所示，圖中五角星表示最短路徑節點。

5 改進前后DD協議的仿真結果及分析

為檢驗改進后算法的整體效果，從網絡中節點的生命周期、路由鏈路的變化、節點剩余能量的均勻程度以及能量的標準差等幾方面進行仿真驗證。

在改進后的定向擴散協議中，由于選擇中間節點時考慮了節點間的距離與剩余能量，從而實現了數據的可靠傳輸，同時傳輸完成后節點的能耗比較均勻[9]。網絡中能量較低的節點不會被選擇作為下一跳，避免了被選節點能夠從源節點一端接收數據但卻不能將其發往匯聚節點一端的情況發生。原始DD協議和改進后DD協議的生命周期對比結果如圖4所示。

原始DD協議和改進后DD協議的動態路由選擇效果圖分別如圖5、圖6所示。在改進后的協議中，數據傳輸鏈路隨著網絡中節點剩余能量的變化而進行動態調整，網絡中的所有節點都會分擔整個網絡數據傳輸任務的負荷量。

在改進后的協議中，網絡節點的能量消耗分布更加均勻，這在一定程度上也延長了整個網絡的生命周期。

原始DD協議和改進后DD協議中各個節點的能耗分布情況分別如圖7、圖8所示。

DD協議改進前后整個網絡能量的標準差變化如圖9所示。從圖9可以看出，當數據傳輸到100輪以后，原始DD協議中節點的能量標準方差逐漸變大，而改進后的DD協議中節點的能量標準方差比原始協議小，說明改進后的協議使得傳感器網絡中節點的能量消耗均勻，符合無線傳感器網絡的設計要求，達到了網絡中節點能量消耗均勻的目的。

6 結 語

本文在現有協議的基礎上對網絡中數據通信過程中下一跳節點的選擇策略進行改進，即在選擇節點的同時考慮節點間的通信距離與節點的剩余能量情況。此協議規則能避免原始協議中能量較少的節點被選為數據傳輸路徑上的負載節點，導致節點能量消耗不均的問題，最終使整個網絡的壽命得到延長，并能提高能量的利用率，保證網絡數據傳輸的服務質量。后續工作可在仿真過程中設置更多的節點并使節點位置具有更強的隨機性。

參考文獻

[1]彭海英，唐伶俐，唐紅.無線傳感器網絡中DD路由協議的改進研究[J].計算機工程與應用，2007，43（14）：127-130.

[2]孫利民，葉馳，廖勇.傳感器網絡的路由機制[J].計算機科學，2004，31（3）：54-57.

[3] DORIGO M，GAMBARDELLA L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE trans on evolutionary computation，1997，1（1）：53-56.

[4]黃翰，郝志峰，吳春國，等.蟻群算法的收斂速度分析[J].計算機學報，2007，30（8）：1344-1353.

[5]汪凱，張貴倉.基于改進蟻群算法的圖像邊緣檢測研究[J].計算機工程與應用，2017，53（23）：171-176.

[6] BELLO R，NOWE A，CABALLERO Y，et al.A model based on ant colony system and rough set theory to feature selection[C]//Genetic and Evolu-tionary Computation Conference，2005.

[7]羅蘭花，梁海英，任子亭.基于改進蟻群算法的網絡能量平衡路由策略[J].機械設計與制造，2017（11）：238-241.

[8]鄭明才，李勇帆，趙小超，等.定向擴散路由無線傳感器網絡行為仿真[J].計算機系統應用，2013，22（5）：143-146.

[9] KANNAMMAL K E，PURUSOTHAMAN T. Performance of improved directed diffusion protocol for sensor networks under different mobility models[J]. Journal of computer science，2012，8（5）：694-700.