林梅金 蘇彩紅 李如雄

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

0 引言

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

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

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

1 系統(tǒng)模型

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

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

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

3) 節(jié)點配備的無線發(fā)射功率模塊的發(fā)射功率大小可調(diào)，即可根據(jù)距離來調(diào)整發(fā)射功率的大小；

signal strength indication, RSSI）。

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

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

2 NDGP

NDGP協(xié)議按輪運行，每輪由簇生成、簇間多跳路由建立和數(shù)據(jù)收集三個階段構(gòu)成。

在簇生成階段網(wǎng)絡完成簇首節(jié)點集、本輪簇內(nèi)活躍普通節(jié)點集和休眠節(jié)點集的確定，簇生成之后簇首為簇內(nèi)活躍成員創(chuàng)建TDMA調(diào)度[9]，并把調(diào)度方案廣播給簇內(nèi)活躍成員，完成簇內(nèi)數(shù)據(jù)的收集。

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

數(shù)據(jù)收集階段，網(wǎng)絡各節(jié)點轉(zhuǎn)換至自己的狀態(tài)（簇首、活躍節(jié)點、休眠節(jié)點），各個簇首按照分配好的TDMA調(diào)度收集簇內(nèi)成員節(jié)點的數(shù)據(jù)，融合數(shù)據(jù)并在既定的時隙將融合數(shù)據(jù)發(fā)送至它的父簇首節(jié)點，此階段持續(xù)至本輪結(jié)束。為了保證網(wǎng)絡的有效工作時間，算法需要網(wǎng)絡運行在數(shù)據(jù)收集階段時間大大超過其它兩個階段的運行時間。

2.1 簇生成階段

2.1.1 最優(yōu)簇半徑計算

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

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

2.1.2 簇內(nèi)活躍節(jié)點數(shù)計算

無線傳感器網(wǎng)絡中，傳感節(jié)點密集部署常常帶來網(wǎng)絡的冗余以及無線信道干擾等問題。本協(xié)議在保證網(wǎng)絡覆蓋率要求的前提下，采用簇內(nèi)調(diào)度減少工作節(jié)點數(shù)目的方法，合理利用節(jié)點能量，使無線傳感器網(wǎng)絡的各種資源得到優(yōu)化分配。

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

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

以簇首節(jié)點為圓心，簇半徑 RC為半徑的圓形區(qū)域中，如果節(jié)點的感知半徑為RS，則簇內(nèi)保證以η為概率監(jiān)測整個簇所需的最少活動節(jié)點數(shù)為：

2.1.3 簇生成階段描述

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

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

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

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

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

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

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

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

2.2 簇間多跳路由建立階段

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

2.3 數(shù)據(jù)收集階段

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

3 仿真實驗

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

表1 仿真實驗參數(shù)

3.1 網(wǎng)絡拓撲

圖1是網(wǎng)絡節(jié)點數(shù)為600時，NDGP協(xié)議生成的網(wǎng)絡拓撲結(jié)構(gòu)圖，可以看出本協(xié)議生成的簇分布均勻，簇首可以經(jīng)過多跳鏈接至基站。

3.2 能耗比較

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

圖1 網(wǎng)絡拓撲結(jié)構(gòu)圖

圖2 能耗對比圖

3.3 網(wǎng)絡壽命比較

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

圖3 節(jié)點數(shù)與網(wǎng)絡壽命（第一個節(jié)點死亡）

圖4 節(jié)點數(shù)與網(wǎng)絡壽命（最后一個節(jié)點死亡）

4 結(jié)論

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

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

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

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

[3] 劉鐵流,巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡分簇路由算法研究[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] 蔣暢江,石為人,唐賢倫,等. 能量均衡的無線傳感器網(wǎng)絡非均勻分簇路由協(xié)議[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] 龔海剛,劉明,余昌遠,等.無線傳感器網(wǎng)絡環(huán)境下基于事件驅(qū)動應用的節(jié)能 TDMA 協(xié)議[J].電子學報,2007,35(10)：1843-1848.

[10] 郭士琪.無線傳感器網(wǎng)絡分簇算法研究綜述[J].經(jīng)營管理者,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.