無線傳感器網(wǎng)絡(luò)中定向擴散路由協(xié)議的研究

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

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；DD協(xié)議；螞蟻算法；網(wǎng)絡(luò)節(jié)點

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

0 引 言

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

1 定向擴散協(xié)議的概念過程分析

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

2 利用蟻群算法模擬實現(xiàn)原始定向擴散路由協(xié)議

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

2.1 算法中各個參數(shù)的初始化操作

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

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

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

（3）為網(wǎng)絡(luò)中的匯聚節(jié)點和源節(jié)點賦予較大的能量初值，將其他節(jié)點視為普通節(jié)點，賦予較小的能量初值。

2.2 算法中路徑的選擇規(guī)則

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

（1）

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

2.3 算法中信息素的更新

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

（2）

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

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

2.4 能量消耗計算

假設(shè)網(wǎng)絡(luò)中有node_A和node_B兩個傳感器節(jié)點，它們之間的距離為d m，當節(jié)點node_A向節(jié)點node_B發(fā)送

k bit數(shù)據(jù)包時，節(jié)點node_A和node_B消耗的能量計算公式

如下[7]：

（3）

（4）

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

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

3 對原始DD協(xié)議的改進

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

（1）計算節(jié)點間的距離：

（5）

（2）計算候選節(jié)點的剩余能量：

（6）

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

（7）

式中u是[0，1]之間的常數(shù)。

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

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

4 原始協(xié)議的仿真

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

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

5 改進前后DD協(xié)議的仿真結(jié)果及分析

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

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

原始DD協(xié)議和改進后DD協(xié)議的動態(tài)路由選擇效果圖分別如圖5、圖6所示。在改進后的協(xié)議中，數(shù)據(jù)傳輸鏈路隨著網(wǎng)絡(luò)中節(jié)點剩余能量的變化而進行動態(tài)調(diào)整，網(wǎng)絡(luò)中的所有節(jié)點都會分擔整個網(wǎng)絡(luò)數(shù)據(jù)傳輸任務(wù)的負荷量。

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

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

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

6 結(jié) 語

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

參考文獻

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

[2]孫利民，葉馳，廖勇.傳感器網(wǎng)絡(luò)的路由機制[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].計算機工程與應(yīng)用，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]羅蘭花，梁海英，任子亭.基于改進蟻群算法的網(wǎng)絡(luò)能量平衡路由策略[J].機械設(shè)計與制造，2017（11）：238-241.

[8]鄭明才，李勇帆，趙小超，等.定向擴散路由無線傳感器網(wǎng)絡(luò)行為仿真[J].計算機系統(tǒng)應(yīng)用，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.