一種新的高能效無線傳感器網絡數據收集協議*

林梅金 蘇彩紅 李如雄

（1.佛山科學技術學院 2.廣東電網公司佛山供電局）

0 引言

近年來隨著傳感器技術、低功耗電子器件和射頻技術的飛速發展，低成本、低能耗、多功能的微型無線傳感節點的大量生產成為發展趨勢[1]。傳感節點隨機或固定地布置在監測環境中，通過特定的協議自組織構成無線傳感器網絡，協同監測周圍環境信息以完成特定任務。而節點通常安裝在環境惡劣甚至危險的遠程場合中，能源難以更換，這使得如何高效利用節點有限的能量以延長傳感器網絡壽命，成為網絡協議設計中需要考慮的首要因素[2]。為了延長整個網絡壽命和提高網絡的利用率，較好的途徑是尋找一種更好的節省網絡節點消耗能量的算法，而分簇正是為了解決這些問題引入對網絡分層方法的重要技術[3]。

Heinzelman W. R.等[4]首次提出低能耗自適應分簇算法（low-energy adaptive clustering hierarchy，LEACH）協議應用在無線傳感器網絡中，該協議以數據為中心構建單層簇，其基本思想是首先按照自組織方式隨機選擇節點作為簇首節點，普通節點選擇離自己最近的簇首節點加入，簇首節點采用分時復用的方式為本簇中每個節點分配數據傳輸的時間隙。簇首融合簇內成員以及簇首自己收集的數據后發送至基站。LEACH算法以隨機方式選擇簇首節點常常導致簇與簇之間分布不均勻，并且所有簇首節點均直接與基站通信，導致離基站較遠的簇首節點因能量消耗很快先行死亡。針對LEACH協議的不足，文獻[5]中提出一種基于鏈的數據收集協議（power-efficient gathering in sensor information systems，PEGASIS）。在PEGASIS協議中，簇首節點只需和離它最近的鄰居簇首節點通信，數據通過多跳傳輸至基站，從而降低了簇首節點的能耗，與LEACH協議相比，獲得了更長的網絡壽命。但是，當網絡中出現過長的通信鏈路時，將導致數據傳輸至基站的能耗增大，不利于延長網絡壽命。文獻[1]指出協議PEGASIS和低能耗的數據收集及融合方法（power efficient data gathering and aggregation，PEDAP）[6]在網絡運行時，由于需要獲取所有節點位置和更新路由信息而產生大量能量開銷等缺點，提出一種基于分簇和近優最小匯集樹的多級路由數據收集協議（energy-efficient data gathering protocol，DEEC-MR），提高網絡的可擴展性和可靠性，延長了網絡壽命。

借鑒前人研究[1-8,11]的優點，本文提出一種新的高效節能數據收集協議—NDGP。該協議具有以下性質：1) 是一種分布式算法；2) 能實現簇首節點在網絡中均勻分布；3) 算法運行能耗低；4) 不要求節點具有特殊的通信能力，即不需要所有節點都能與sink節點直接通信。

1 系統模型

無線傳感器網絡完成一次網絡拓撲構建并且運行一段時間進行數據收集，稱為一“輪”。NDGP協議按輪運行，網絡中傳感節點周期性地充當簇首節點（cluster head, CH）或者普通節點（ordinary node, ON）進行環境監測及數據轉發。文中假定將N個無線傳感節點隨機均勻分布在一個M×M的正方形區域中，并進行了以下幾點假設：

1) 所有傳感節點部署后位置固定，且被賦予唯一的標號，傳感節點的能量有限，而基站有專門的供電系統；

2) 基站部署在監測區域幾何中心上，位置固定且是唯一的；

3) 節點配備的無線發射功率模塊的發射功率大小可調，即可根據距離來調整發射功率的大小；

signal strength indication, RSSI）。

本文采用文獻[9]提出的無線通信模型，節點收、發數據的能耗通過式(1)和式(2)計算。

其中，ETX(i, j)、ERX(i, j)表示節點i發送至節點j、接收到節點j信息的能耗；k表示節點發送或接收的數據位數；Eelec表示無線收發電路消耗的能量；Eamp表示天線增益消耗的能量；di,j表示節點i與節點j的歐氏距離。該模型給出了一個閾值d0（d0是常數，數值取決于使用環境）。當發送節點與接收節點距離小于d0時，發送方發送數據的能量損耗與距離的平方成正比（ε=2），此時能耗模型對應的是自由空間模型；當發送節點與接收節點距離大于d0時，發送方發送數據的能量損耗與距離的四次方成正比（ε=4），此時能耗模型對應的是多路衰減模型。

2 NDGP

NDGP協議按輪運行，每輪由簇生成、簇間多跳路由建立和數據收集三個階段構成。

在簇生成階段網絡完成簇首節點集、本輪簇內活躍普通節點集和休眠節點集的確定，簇生成之后簇首為簇內活躍成員創建TDMA調度[9]，并把調度方案廣播給簇內活躍成員，完成簇內數據的收集。

簇間多跳路由建立階段生成以基站為根，簇首為節點的鏈狀多跳路由，使得數據在各簇首節點之間以多跳方式傳輸至基站。

數據收集階段，網絡各節點轉換至自己的狀態（簇首、活躍節點、休眠節點），各個簇首按照分配好的TDMA調度收集簇內成員節點的數據，融合數據并在既定的時隙將融合數據發送至它的父簇首節點，此階段持續至本輪結束。為了保證網絡的有效工作時間，算法需要網絡運行在數據收集階段時間大大超過其它兩個階段的運行時間。

2.1 簇生成階段

2.1.1 最優簇半徑計算

在無線傳感器網絡中，簇首節點的數量是衡量一個分簇算法優劣的標準之一[10]。簇半徑 RC決定著網絡中簇的數量，直接影響整個系統的能耗。根據文獻[1]的最優簇半徑計算思想，當基站位于監控區域幾何中心時，簇首與基站間距離的數學期望值為因此對文獻[1]的式(16)進行修改后，可獲得網絡采集一次數據并傳輸至基站的總能耗

本文研究了網絡節點數80至250變化范圍，網絡覆蓋率大于 90%，此時計算獲得使 Etotal為最小的RC分布在62至68之間。為了保證網絡較大的覆蓋率，且盡可能減少網絡能量消耗，本文折中取值RC=65。

2.1.2 簇內活躍節點數計算

無線傳感器網絡中，傳感節點密集部署常常帶來網絡的冗余以及無線信道干擾等問題。本協議在保證網絡覆蓋率要求的前提下，采用簇內調度減少工作節點數目的方法，合理利用節點能量，使無線傳感器網絡的各種資源得到優化分配。

假設在監測區域Area（其面積為A= π RC2）中，布置1個感知半徑為RS的傳感節點N，可知N的覆蓋面積為SN= π RS2，則節點N能監測整個區域Area的概率為PN=(RS/RC)2，Area中任意一點不被節點 N監測到的概率為=1－(RS/RC)2。

在Area中隨機且均勻布置k個感知半徑為RS的傳感節點，則 Area中任意一點不被任何節點監測到的概率為：=（1－(RS/RC)2）k。

以簇首節點為圓心，簇半徑 RC為半徑的圓形區域中，如果節點的感知半徑為RS，則簇內保證以η為概率監測整個簇所需的最少活動節點數為：

2.1.3 簇生成階段描述

NDGP采用基于競爭機制的分布式簇生成算法，簇生成階段由基站發起，喚起監測區域內的所有節點同步進入簇生成階段，并由上一輪數據收集階段獲取網絡中節點的最大剩余能量值（emax）信息告知各節點。該消息格式

網絡中的傳感節點根據接收基站發送信號強度rssi，計算并保存自己與基站的距離rssi (i, bs)。然后，每個節點根據自身的剩余能量ecur(i)以及rssi (i, bs)計算發送競爭簇首的延遲時間tdelay(i)

為了保證最大剩余能量有更大的機率競爭上簇首位置，σ取值[0.9,1]，為了避免兩個距離小于 RC的等能量節點在簇首競爭時發生沖突，在tdelay(i)表達式中引入rand (i)微擾動信號。為了避免距離基站過近的節點成為簇首節點，在 tdelay(i)中引入因子

網絡中節點i在0至tdelay(i)時間段內不斷接收其它節點申明自己為簇首節點的簇首廣播消息（CH_msg），消息格式

若延遲 tdelay(i)時間到達，判斷沒有接收到任何CH_msg，則立即向半徑為RC的范圍內發送CH_msg，申明自己為簇首。若延遲時間tdelay(i)到達，節點i接收到幾幀CH_msg，則選擇離基站最近的CH_msg作為自己的簇首節點，并發送Join_CH_msg，消息格式

由tdelay(i)的計算式可知，不等式tdelay(i)＜t0成立，因此在基站發出同步信號后的t0時刻，監測區域Area內的傳感節點要么成為簇首節點，要么成為普通節點。此時各簇首根據式(4)計算kmin，并根據簇內成員的 ecur，選擇本輪數據采集階段的活躍節點，并為它們分配通信時隙。

綜上所述，可得算法如下：

簇生成階段后，各簇首通知各成員節點進入休眠狀態，在簇間多跳路由建立期間，普通成員不需要參加，只需要簇首成員和基站參與即可。

2.2 簇間多跳路由建立階段

基站自簇生成階段發送的同步信號后t0+1時刻，開始向半徑為RC的范圍內廣播建立多跳路由廣播消息 FS_msg（FatherSon_message，尋找父子關系消息）。該消息格式

2.3 數據收集階段

簇間多跳路由建立自基站發送FS_msg同步信號后在 pt1時間內完成，此時基站將數據收集階段開始的同步信號發至網絡中的所有節點。普通活躍節點蘇醒并根據簇內TDMA調度時隙將監測數據發至簇首節點，簇首節點將收到的簇內數據融合處理后連同本簇首節點采集的數據轉發至其父簇首節點，網絡中的普通休眠節點繼續休眠保存能量，直到本階段結束。

3 仿真實驗

利用Matlab編寫模擬程序，將NGDP協議與文獻[1]中的DEEC-MR協議和文獻[4]中的LEACH協議進行仿真并比較。網絡環境的配置參數如表1所示。在網絡實驗中，考慮兩種網絡壽命的定義：第一個節點死亡和最后一個節點死亡的時間，當節點剩余能量小于0.002J時，認為該節點死亡。實驗中模擬了節點數量變化對協議性能的影響。

表1 仿真實驗參數

3.1 網絡拓撲

圖1是網絡節點數為600時，NDGP協議生成的網絡拓撲結構圖，可以看出本協議生成的簇分布均勻，簇首可以經過多跳鏈接至基站。

3.2 能耗比較

本文對比了不同算法采集一次數據并傳輸至基站的能耗隨網絡節點數的變化情況。圖2是幾種算法在不同網絡節點數下的能耗對比圖，該曲線情況反映了網絡數據收集的效率。由圖2可看出，LEACH協議的能耗最高，其原因是該協議將數據從簇首傳送至基站采用單跳方式。NDGP協議相比DEEC-MR協議，當網絡節點數越大，NDGP的效率比協議DEEC-MR運行效率更好，原因是NDGP協議中保存冗余節點能量的機制比DEEC-MR要好。

圖1 網絡拓撲結構圖

圖2 能耗對比圖

3.3 網絡壽命比較

仿真研究當監控區域的節點數量增加時，網絡壽命的變化情況見圖3和圖4。無線傳感器網絡協議的性能常常以首個節點死亡時間為主要依據，首個節點死亡出現得越晚，死亡時間越集中，則協議的性能越好。LEACH協議根據概率選擇簇首的算法使得簇覆蓋面隨著節點密度的增加而減小，這種辦法無法有效利用簇首的數據融合優勢，因此LEACH協議的網絡壽命并沒有隨著網絡節點數量的增加而明顯提高。NDGP協議中節點開始死亡的時間晚于DEEC-MR協議，死亡時間的集中程度NDGP協議在節點密度高的場合略優于 DEEC-MR協議，但兩者均大大優于LEACH協議。NDGP協議運行總輪數比DEEC-MR、LEACH協議多，其主要原因是：1）NDGP協議在簇首多跳建立階段有防止孤立簇的機制，這有利于避免因多跳路由引起的能量空洞而造成網絡運行中止的現象；2) 在保證用戶覆蓋率的前提下，NDGP協議有令網絡內冗余節點進入休眠狀態的機制，從而有效地延長了網絡壽命，并且該機制在網絡節點密度大的場合優勢更加明顯。

圖3 節點數與網絡壽命（第一個節點死亡）

圖4 節點數與網絡壽命（最后一個節點死亡）

4 結論

本文針對大規模無線傳感器網絡中收集數據的需要，提出一種新的高能效數據收集協議—NDGP。該協議在簇的生成階段可保證高剩余能量的節點成為簇首節點，采用微擾動的辦法解決了競爭簇首時通信堵塞的問題，成功實現均勻分簇。NDGP協議通過簇首節點執行

數據融合和數據收集階段冗余節點進入休眠狀態等機制，從而有效地節省網絡的能耗。仿真結果表明：與LEACH協議和DEEC-MR協議相比較，NDGP具有更好的運行效率和更長的網絡壽命，更適合于高密度、大規模無線傳感器網絡的應用。然而，在節點均勻分布的網絡運行后期，由于靠近基站的簇首節點承擔了更重的數據轉發任務，導致這些簇首節點會先行死亡。因此，NDGP也不可避免地存在監控網絡能量空洞的問題。

[1] 史久根,胡小博.高效節能的無線傳感器網絡數據收集協議[J].電子測量與儀器學報,2012,26(5)： 437-444.

[2] 杜冬梅,張志,何青,等.無線傳感器網絡節能技術分析[J].儀器儀表學報,2006,27(6)：366-367.

[3] 劉鐵流,巫詠群.基于能量優化的無線傳感器網絡分簇路由算法研究[J].傳感技術學報,2010,24(5)：764-769.

[4] Heinzelman W R, Chandrakasan A, Balakrishnan H.Energy-efficient communication protocol for wireless micro-sensor networks[C]. 33rdAnnual Hawaii International Conference on System Sciences, Hawaii, 2000： 1-10.

[5] Lindsey S，Raghavendra C．Pegasis： Power-efficient gathering in sensor information systems[J]．IEEE Transactions on Parallel and Distributed Systems, 2002,13(9)：924-932.

[6] Tan H O,Korpeoglu I. Power efficient data gathering and aggregation in wireless sensor networks[J]. ACM SIGMOD Record, 2003,32(4)：66-71.

[7] 蔣暢江,石為人,唐賢倫,等. 能量均衡的無線傳感器網絡非均勻分簇路由協議[J].軟件學報, 2012, 23(5)： 1223-1232.

[8] Xiang M, Shi WR, Jiang CJ, et al. Energy efficient clustering algorithm for maximizing lifetime of wireless sensor networks.AEU-Int’l Journal of Electronic and Communication, 2010,64(4)：289-298.

[9] 龔海剛,劉明,余昌遠,等.無線傳感器網絡環境下基于事件驅動應用的節能 TDMA 協議[J].電子學報,2007,35(10)：1843-1848.

[10] 郭士琪.無線傳感器網絡分簇算法研究綜述[J].經營管理者,2012(9)：367-367.

[11] Zhixin Liu, Qingchao Zheng, Liang Xue, et al. A distributed energy-efficient clustering algorithm with improved coverage in wireless sensor networks[J]. Future Generation Computer Systems, 2012,28(5)：780-790.