分區域的樹型多鏈的無線傳感器網絡路由算法

方旺盛，彭美平，胡中棟

（江西理工大學 信息工程學院，江西 贛州 341000）

無線傳感器網絡（Wireless Sensor Network，WSN）廣泛應用于智慧農業、環境監控、戰場監控和動物跟蹤等方面，其由傳感模塊、存儲模塊、計算模塊、電源模塊組成。由于傳感器節點體積小，自身的計算、通信能力及存儲能量有限，WSN監測的區域廣，部署的傳感器節點眾多，無法為大量傳感器節點更換電池等缺陷，使得有效節省全網節點能耗成為需要解決的重要問題。路由協議是影響傳感器節點能耗的主要因素之一，也是提高無線傳感器網絡壽命的一個關鍵因素，其中分簇路由協議是路由協議的一類，因其節省能耗而被廣泛應用?；诖?，本文提出一種分區域的樹型多鏈的無線傳感器網絡路由算法。

1 經典分簇路由算法分析

1.1 LEACH算法

LEACH算法將全網節點分成幾個簇，簇內能進行數據融合，可節省能耗，但簇頭節點需進行數據計算，直接與sink節點通信等需消耗較多能量，會造成全網節點能量不均衡。因此LEACH算法會不斷進行簇重構、簇頭的重新選舉，這將會增加額外的能耗。

1.2 PEGASIS算法

PEGASIS（Power-Efficient GAthering in Sensor Information Systems）算法將全網節點形成一條長鏈，鏈中相鄰兩節點間的距離相對較短，且數據傳輸時節點輪流當選鏈頭與sink節點通信，不用簇的重構、簇頭的重新選舉等，節省了開銷。但PEGASIS算法仍然存在以下不足：第一，若無線傳感器網絡中節點數目較多，連接過程中形成一條長鏈，會存在鏈的交叉、數據逆傳等問題，節點能量利用率不高；第二，在所構建的鏈中，遠距離的節點會引起過多的數據延時；第三，該協議所成鏈中只有一個鏈頭節點，使得鏈頭節點成為整個網絡的瓶頸。

1.3 COSEN算法

COSEN（A Chain Oriented Sensor Network）算法將整個全網所有節點形成的一條長鏈拆成幾條短鏈，減少了鏈路長度，每條分鏈同時收集數據進行處理、融合，大大降低了網絡時延。當網絡中某個節點死亡時，只對當前分鏈和鏈頭節點形成的主鏈進行維護，維護成本相對較低。但依然存在如下不足：第一，鏈內存在交叉，易造成數據的回傳；第二，鏈間存在交叉，易造成算法的局部最優。

2 本文算法

針對COSEN算法存在的缺陷，文獻[11]提出一種多級分層鏈路算法。該算法按照節點與基站的距離對全網節點分層，每層節點之間采用貪婪式的方法形成一條鏈。該算法雖然大幅降低了全網總能耗，但仍然存在缺陷：第一，若縱向的不在同層的2個節點相距較近，則無法連接到一條鏈，容易造成節點間跨度較大，增加能耗；第二，節點容易形成橫向跨度較大的長鏈，從而造成節點的檢測數據差別較大，不利于數據融合；第三，若sink節點在網絡區域內部，將形成半圓環的鏈或圓環的鏈，內鏈長度短，外鏈長度長，易造成節點能量消耗不均衡。鑒于以上討論，首先，本文算法將全網節點根據數據的相關性分為若干個長條狀的區域，克服文獻[11]算法中縱向的不同層次的2個節點相距較近，而無法連接到一條鏈的情況；其次，本文算法區域中的節點根據它們之間的距離和角度形成樹型結構的鏈，克服文獻[11]算法中橫向成鏈使整條鏈較長，從而節點的檢測數據差別較大，不利于數據融合的問題；最后，本文算法將sink節點部署在網絡區域，彌補文獻[11]算法中sink節點部署在網絡區域內能量消耗不均衡的情況。

2.1 算法設計思路

本文算法根據數據的相關性，將全網區域分成若干個長條狀的區域，在每個區域中根據節點之間的距離和角度連接成一條鏈。成鏈過程中若產生交叉鏈，刪除兩交叉鏈中鏈較長的那個，這樣會產生孤立節點，各個分區域內的孤立節點找本區域中已經成鏈的節點連接；區域外的孤立節點也找到已經成鏈的節點連接，這樣就形成了分區域的樹型多鏈結構。各分鏈鏈頭根據它們之間的距離和角度連接形成樹型主鏈，主鏈鏈頭與sink節點通信，或者各分鏈鏈頭直接與sink節點通信，即各分鏈鏈頭采用單跳和多跳相結合的方式與sink節點通信。

2.1.1 無線傳感器網絡分區

在無線傳感器網絡中，當傳感器節點在網絡區域隨機部署完畢后，節點將檢測數據發給鄰居節點，鄰居節點根據收到的數據將從離sink節點近的節點開始依次向外將全網區域分成若干區域。在分區域過程中判斷該區域是否為長條狀區域，即區域的長寬是否在上下閾值之間。若區域的長寬低于上下閾值，則區域中加入新的節點；若區域的長寬超過上下閾值，則區域中去掉加入的節點或者更換節點加入，直到整個分區域在上下閾值之間。從離sink節點近的節點開始依次向外劃分，直到所有區域劃分為長條狀區域。對于網絡邊緣的區域，節點往往比較稀疏，網絡區域可以不滿足設定閾值，只要節點能量消耗小即可。分區域流程如圖1所示。

圖1 分區域流程圖

分區過程的偽代碼如下：

2.1.2 區域內的節點連接成鏈

將整個網絡區域分成幾個長條狀的區域后，在每個子區域中根據節點之間的距離和角度將節點連接成一條鏈，具體成鏈過程如下：

如圖2所示，在一個分區域中，節點為該區域的終節點，節點為將要成鏈的節點，以節點為例來說明具體成鏈的過程。節點的下一跳節點從它的相鄰節點中選取，有，，，，，共6個節點。選擇哪個節點作為節點的下一跳節點，取決于下式：

式中：d 為節點到節點的下一跳節點的距離；為節點到節點連線與節點到下一跳節點連線的夾角。將，，，，，共6個節點代入式（1），顯然，W ＜W ＜W ＜W ＜W =W =，選擇使W 值最小的節點為下一跳節點。然后依據式（1），用節點和它下一跳節點之間的距離和角度兩個因素相結合的方式將節點連接起來形成一條鏈，若成鏈過程中產生交叉鏈，刪除兩交叉鏈中鏈較長的那個，這樣可形成分區域的主干鏈。

區域中的節點形成主干鏈的過程中，會產生如圖2中，，，，這樣的孤立節點。這些孤立節點按照式（1）找到本區域中使它們的值最小的下一跳節點連接。

圖2 區域內節點連接成鏈

圖3中節點、節點、節點分別與已成鏈節點、節點、節點建立連接。

若根據式（1），使孤立節點最小值的下一跳節點不在主干鏈上，那么離已成鏈節點近的孤立節點先根據式（1）找到使孤立節點最小值的下一跳節點，并計算值；然后找到孤立節點的下一跳在主干鏈上的節點，計算它們的值。最小的值記為；最小的值記為；最后比較和的值，找到值最小的下一跳節點連接。值計算公式如下：

式中：d 為節點到節點的下一跳節點的距離；為節點到節點連線與節點到下一跳節點連線的夾角；為節點要連的下一跳節點所在分支鏈中的節點個數。若孤立節點，使它的值最小的下一跳節點為節點，節點的最小值的下一跳節點為節點，節點和節點都不在主干鏈中，節點離已成鏈節點較近，為分支鏈中的第一個節點，且已連接到鏈中；接著節點離已成鏈節點較近，根據式（2）找到使節點最小值的下一跳節點為節點，并計算F 的值；然后在節點的鄰居節點中找到下一跳在主干鏈上的節點，節點是節點下一跳在主干鏈上的節點中值最小節點，并計算W 的值。因為節點F ＜W ，所以節點的下一跳節點為節點。同理，因為W ＜F ，所以節點的下一跳節點為節點。區域中的孤立節點的鏈接如圖3所示。

圖3 區域內孤立節點連接成鏈

2.1.3 區域外的節點連接成鏈

分區域外的孤立節點分別找使它們的值最小的下一跳已成鏈節點連接成鏈，如圖4中的節點、節點分別與已成鏈節點、節點連接。

圖4 區域外的節點連接成鏈

2.1.4 鏈頭節點的選舉及通信

在形成的各條分鏈中，鏈中節點輪流當鏈頭，輪流的原則遵循相鄰鏈的鏈頭之間的距離盡可能小。

各分鏈選出鏈頭節點后，分鏈鏈頭與sink節點的通信采用文獻[13]中單跳和多跳相結合的通信方式。單跳時遠處分鏈的鏈頭節點耗能大，多跳時近處分鏈的鏈頭節點耗能大。節點總的數據通信時間為，在·時間內，分鏈鏈頭以單跳的方式與sink節點通信；在·( 1-)的時間內，分鏈鏈頭以多跳的方式與sink節點通信。

分鏈鏈頭的多跳傳輸需要成鏈，成鏈的規則和各分區域節點的成鏈規則一樣，即根據鏈頭節點之間的距離和角度形成樹型主鏈。樹型主鏈找到離sink節點最近的節點充當主鏈鏈頭與sink節點通信。全網節點具體成鏈情況如圖5所示。

圖5 全網節點所成鏈路

2.2 算法偽代碼

3 算法仿真與分析

本文設定的實驗區域為100 m×100 m，區域中部署100個傳感器節點?？紤]到數據的相關性、鏈的長度、網絡整體的時延及能耗，將整個傳感器網絡區域分為6個長條狀的區域，長條狀區域的長、寬的上閾值分別為100 m，20 m，下閾值為35 m，5 m。

本文采用Matlab仿真實驗，并與在本區域中利用PEGASIS算法、COSEN算法、文獻[11]的MSLR（Multistage Stratified Link Routing）算法進行仿真實驗的結果進行對比，從節點的成鏈情況、節點死亡數目、網絡能量消耗和時延四個方面進行分析評估。算法的仿真參數如表1所示。

表1 仿真參數

3.1 節點成鏈情況

圖6中的4幅仿真圖分別為PEGASIS算法、COSEN算法、MSLR算法和本文算法形成的仿真圖。將四種算法成鏈情況做對比可以看出：前兩種算法形成的鏈存在明顯的交叉，整體較亂；而MSLR算法雖然比前兩種算法有條理，但依然存在鏈間交叉和某些鏈較長的問題；本文算法形成的樹型結構有明顯的條理且無交叉，相比PEGASIS算法形成的鏈較短，相比COSEN算法和MSLR算法形成的鏈無交叉，可避免數據的回傳。

圖6 各算法鏈式圖對比

3.2 能耗分析

本文以網絡區域中全部節點到sink節點的一次數據傳輸為一個周期，對比四種算法在工作過程中節點的死亡數目和全網能量消耗情況，如圖7、圖8所示。從圖7可以看出，本文算法比前三種算法的首個節點的死亡數量和全網所有節點的死亡數量都有所延長。本文算法的首個節點死亡的輪數大約在660輪，比PEGASIS算法、COSEN算法、MSLR算法的首個節點死亡的輪數分別延長了大約260輪、140輪、100輪。

圖7 每輪死亡節點數對比

本文算法的全網全部節點死亡的輪數大約在920輪，比PEGASIS算法、COSEN算法、MSLR算法的全網全部節點死亡的輪數分別延長了大約180輪、90輪、70輪，本文算法生命周期有所延長。

從圖8的全網節點能量消耗對比的仿真圖可以看出，PEGASIS算法在740輪時全網能量基本消耗完畢，COSEN算法全網能量基本消耗完在830輪，MSLR算法在850輪時全網能量基本消耗完畢，本文的算法全網能量基本消耗完畢在920輪，在同一周期內比PEGASIS算法、COSEN算法和MSLR算法的全網節點能量消耗都小。

圖8 全網節點能量消耗對比

3.3 時延分析

圖9是四種算法從節點開始工作到第一個節點死亡時間內的時延情況對比仿真圖。

圖9 節點時延情況對比

從圖9可以看出，本文算法時延最短，PEGASIS算法時延最長，并且比另外兩種算法時延大得多。原因在于PEGASIS算法全網形成一條鏈，只有一個鏈頭與sink節點通信，所以時延較大；COSEN算法和MSLR算法形成多條分鏈，分鏈節點同時傳輸數據，減少了時延。而本文算法將全網節點也分為幾條短鏈，鏈中節點可同時傳輸數據，且短鏈是樹型結構，相鄰兩節點相距較小，鏈中無交叉傳遞數據，所以比其他兩種算法的時延都小。

4 結 語

本文通過將無線傳感器網絡分成長條狀的區域，區域中的節點根據距離和角度連接成鏈，減少了節點之間的距離，使全網節點數據傳輸時延減??；并且區域中的節點之間無交叉，避免了數據的逆傳遞，減少了網絡整體能耗。從整體上來看，節點傳輸數據時延縮短，節點的生命周期有所提升。

注：本文通訊作者為彭美平。