基于蜂巢狀虛擬結構的單匯聚節(jié)點節(jié)能重定位策略*

黃　祺， 馮　勇， 李修琪， 黃北北

(昆明理工大學 計算機重點實驗室，云南 昆明 650504)

?

基于蜂巢狀虛擬結構的單匯聚節(jié)點節(jié)能重定位策略*

黃祺， 馮勇， 李修琪， 黃北北

(昆明理工大學 計算機重點實驗室，云南 昆明 650504)

摘要:提出了一種基于蜂巢狀虛擬結構的單匯聚節(jié)點節(jié)能重定位(HEESR)策略。此策略中整個網絡覆蓋區(qū)域被劃分成多個蜂巢狀虛擬網格結構。匯聚節(jié)點周期性地收集周邊虛擬蜂巢網格的平均剩余能量和網格內單個節(jié)點的剩余能量，基于這些信息匯聚節(jié)點進行重定位。為進一步提高能量效率，HEESR策略還采用基于剩余能量水平的通信半徑調整機制。仿真實驗表明：與現(xiàn)有幾種匯聚節(jié)點重定位方法相比，HEESR能夠更有效地降低能量消耗、延長網絡壽命。

關鍵詞:無線傳感器網絡； 匯聚節(jié)點重定位； 蜂巢虛擬網格； 網絡壽命

0引言

通常無線傳感器所能攜帶的電池能量會十分有限，如何高效利用有限的能量是當前無線傳感器網絡(WSNs)研究的一個重要領域。在當前研究階段，通常考慮使用匯聚節(jié)點來集中處理感知到的數據信息。但如果匯聚節(jié)點始終保持靜止，隨著時間的推移，不均衡的能耗將會導致嚴重的熱點問題和能量空洞[1～3]。引起這一現(xiàn)象的原因在于越接近匯聚節(jié)點，就會被越多的傳輸路徑所共享。目前研究中，運用虛擬分層的方法可以將無線傳感器網絡劃分成兩個或更多的網絡層，分層方法[4]可以分為5種類型，分別是簇、網格、多叉樹、骨干網和指定區(qū)域。

基于網格的方法是將網絡劃分成多層次網格的虛擬層次結構[5]。選擇固定的節(jié)點或者具體坐標來構成交叉區(qū)域的網格。由于網格是一個幾何結構，并且每個傳感器節(jié)點的地理坐標都需要被知曉，因此，地理位置感知傳感器是基于網格方法的首選。

基于簇的方法使用了分簇機制將網絡分層，并在每層或者每個網格中使用簇頭作為高層次收集轉發(fā)節(jié)點[6]。每個簇頭加入一個且只能加入一個最近的簇，并感知收集其所在簇中的數據。相比于網格來說，成簇要更加復雜困難。然而，由于簇是參照節(jié)點拓撲感知信息建立的，虛擬層次結構實現(xiàn)也尤為有效。

基于樹的方法將匯聚節(jié)點作為整個傳輸網絡的根節(jié)點，普通無線傳感器節(jié)點則是葉節(jié)點[7]。除葉節(jié)點外，其余節(jié)點均為高層次節(jié)點。和基于網格類似，這些節(jié)點同時也是源節(jié)點。

基于骨干網的方法中源節(jié)點通過骨干網來向匯聚節(jié)點傳輸感知信息[8]。骨干網由網關節(jié)點和簇節(jié)點組成。骨干網較為適用于延遲容忍網絡，因為只有當匯聚節(jié)點靠近所選擇的網關時會傳輸聚合數據。

基于指定區(qū)域的方法指定在特定區(qū)域中的節(jié)點作為分層結構中的高層節(jié)點，而不是建立復雜的結構[9]。這種層級構造的成本和其他方法構造方法相比是最小的。在避免改變劃分結構的基礎上，為了減輕熱點問題，特定區(qū)域的大小必須足夠大，以減少對高層次節(jié)點負載。

本文提出了一種基于蜂窩網格的匯聚節(jié)點重定位(HEESR)策略。實驗結果表明：HEESR策略能有效均衡傳感器節(jié)點的能耗，并延長網絡壽命。

1HEESR策略

1.1網格模型

首先，在頂點到幾何中心等距(距離為R)的多邊形中，能夠完整且無重疊覆蓋某一區(qū)域的形狀有正三角形、正方形和正六邊形(蜂窩網格)，但是在這三者中，只有正六邊形所覆蓋的面積最大，其次蜂窩網格具有當圓心處于形心時，所用圓的數量最少的數學特性，最后因為考慮到實際運用中所需設備成本的問題，本方法采用了蜂窩網格。用蜂窩網格來實現(xiàn)無線傳感器網絡，可以實現(xiàn)低成本高效率的大面積覆蓋。當區(qū)域給定，有限的資源可以在一定條件下重復利用。當區(qū)域內的資源飽和過剩時，可以將蜂窩網格更加細致的劃分，從而得到更多的蜂窩網格，進一步提升資源利用率。

圖1　網格模型與移動策略Fig 1　Grid model and mobile strategy

1.2HEESR

如圖1所示,明顯能看出除匯聚節(jié)點Sink自身所在的蜂巢網格e，周邊有六個網格a,b,d,f,g,h，分別用 (1≤i≤6)表示。這六個蜂巢網格的形心即為Sink下一步移動的候選位置。用H*來記錄Sink曾經移動的位置。因為節(jié)點隨機分布，每個網格中節(jié)點數目Si不一致，最低為0。分別給予六個網格一個權值wi，wi代表每個網格的平均剩余能量。將R(n)設為每個網格總剩余能量，則wi=R(n)/Si。每隔一定時間，通過能量感知路由協(xié)議MCP[10]，匯聚節(jié)點Sink收集Hi的剩余能量信息wi和每個節(jié)點的信息。其wmin≤…

圖2　HEESR流程圖Fig 2　Flowchart of HEESR

依據判斷所得權值wmv，Sink選擇移動的位置。當數據信息收集處理完畢，匯聚節(jié)點Sink就會以一個恒定的速度向選擇的網格中心移動。當Sink到達預定位置，整個網絡中的拓撲就會依據Sink的當前位置產生變化。Sink會在當前位置停留一定時間來實時地收集數據信息。依據網絡中能量變化，匯聚節(jié)點Sink重定位的過程會一直持續(xù)下去，直至網絡中第一個節(jié)點死亡。

圖3顯示了Sink移動后網絡路由路徑變化，其中,每個圓代表一個網格?？梢钥闯霎擲ink從H1移動到H2時，只有一條路徑的方向發(fā)生了改變。

圖3　Sink重定位后路由路徑的變化Fig 3　Routing path change after sink relocation

1.3傳輸半徑調整機制

2性能分析

2.1能耗模型

本文中所用的無線通信能量模型與文獻[11,12]相同。該無線通信模型給出了一個閾值d(d是常數，數值取決于使用環(huán)境)。根據發(fā)射和接收節(jié)點之間的距離，傳感器節(jié)點可以分別計算發(fā)送和傳輸數據時所需要的能量。當傳感器節(jié)點p向距離d外的另一個節(jié)點q發(fā)送k字節(jié)的數據時，它可以用下面的式(1)來計算能耗

Es(k,d)=Eelec·k+Eamp·k·dn.

(1)

當節(jié)點q接收p發(fā)送的消息時，則用式(2)來計算能耗

Er(k,d)=Eelec·k,

(2)

在上述公式中Eelec為由所述傳感器節(jié)點收發(fā)電路時所消耗的能量。Eamp為由放大器所消耗的能量。因為所有傳感器節(jié)點位置保持不變，所以,節(jié)點p向節(jié)點q傳輸k字節(jié)產生的能耗與節(jié)點q向節(jié)點p傳輸k字節(jié)產生的能耗相等。

2.2參數設置

本文中，所有普通傳感器節(jié)點都以靜止的方式隨機部署在仿真環(huán)境中匯聚節(jié)點是唯一具有移動能力的特殊節(jié)點。當網絡中第一個節(jié)點死亡時，網絡被認為是已死亡。

表1　默認實驗參數

圖4　節(jié)點數目對網絡壽命的影響Fig 4　Effect of number of nodes on network lifetime

圖5　節(jié)點初始能量對網絡壽命的影響Fig 5　Effect of initial energy on network lifetime

圖6　傳輸半徑對網絡壽命影響Fig 6　Effect of transmission radius on network lifetime

圖7　仿真環(huán)境大小對網絡壽命的影響Fig 7　Effect of size of simulation area on network lifetime

3結論

本文提出了HEESR策略,基于鄰居網格中節(jié)點的剩余能耗和網格的平均剩余能量，匯聚節(jié)點可以向周邊六個網格進行移動。仿真實驗表明：HEESR策略能夠有效降低傳感器節(jié)點的傳輸負載和能耗，達到更長的網絡壽命。在接下來的研究中，會考慮當節(jié)點平均能量下降到預定閾值時，調整網絡虛擬網格大小和采用多匯聚節(jié)點數目時的匯聚節(jié)點重定位策略。

參考文獻:

[1]吳曉培,吳躍,陳湘.密集傳感器網絡中節(jié)點隨機調度算法研究[J].電子科技大學學報,2010,39(1):119-122.

[2]馬玉芳,陳建華,郝楊滿.基于匯聚節(jié)點移動的能量均衡路由協(xié)議的研究[J].計算機工程與應用,2013,49(14):77-80.

[3]吳小兵,陳貴海.無線傳感器網絡中節(jié)點非均勻分布的能量空洞問題[J].計算機學報，2008(2):253-261.

[4]Tunca Can,Sinan Isik,Donmez M Yunus,et al.Distributed mobile sink routing for wireless sensor networks:A survey[J].IEEE Communications Surveys & Tutorials,2014,16:877-897.

[5]Luo H,Ye F,Chen J,et al.TTDD:Two-tier data dissemination in large-scale wireless sensor networks[J].Wireless Networks,2005,11(1/2):161-175.

[6]Yuan.Xunxin,Zhang Ruihua.An energy-efficient mobile sink routing algorithm for wireless sensor networks[C]∥Proc of Wireless Communications Conf Networking and Mobile Computing,Wuhan,2011:1-4.

[7]Kim H S,Abdelzaher T F,Kwon W H.Minimum-energy asynchronous dissemination to mobile sinks in wireless sensor networks[C]∥Int’l Conf on Embedded Networked Sensor Systems,SenSys,03,New York,2003:193-204.

[8] Lu J L,Valois F.On the data dissemination in WSNs[C]∥Conf on Wireless Communications,Networking and Mobile Computing,New York,2007:58.

[9] Tunca C,Donmez M Y,Isik S,et al.Ring routing:An energy-efficient routing protocol for wireless sensor networks with a mobile sink[C]∥2012 4th Int’l Conf on Signal Processing and Communications Applications,Fethiye,Mugla,Turkey:2012:1-4.

[10] Wang Chufu ,Shih Jauder ,Pan Bohan,et al. A network lifetime enhancement method for sink relocation and its analysis in wireless sensor networks[J].IEEE Sensors Journal,2014,14(6):1932-1943.

[11] 劉明,龔海剛,毛鶯池,等.高效節(jié)能的傳感器網絡數據收集和聚合協(xié)議[J].軟件學報，2005,16(12):2106-2116.

[12] Sun Yi,Wei Huangfu,Sun Limin,et al.Moving schemes for mobile sinks in wireless sensor networks[C]∥International Perfor-mance Computing and Communications Conference,New Orleans,Louisiana,2007:101-108.

A strategy for energy-efficient relocation of single sink node based on honeycomb virtual structure*

HUANG Qi, FENG Yong, LI Xiu-qi, HUANG Bei-bei

(Yunnan Key Laboratory of Computer Technology Application,Kunming University of Science and Technology,Kunming 650504,China)

Abstract:Propose a strategy for virtual honeycomb-based structured energy-efficient single sink node relocation (HEESR).In this method,overall network coverage field is divided into several honeycomb virtual grid structure Sink node periodicly collect average residual energy of surrounding grids and residual energy of single node within grids and sink node is relocated based on these information.In order to increase energy efficiency,a radius adjustment strategy is used.Simulation shows that HEESR can significantly reduce energy consumption,improve network lifetime,compared with other methods of sink node relocation.

Key words:wireless sensor networks(WSNs); sink node relocation; honeycomb virtual grid; network lifetime

DOI:10.13873/J.1000—9787(2016)03—0133—04

收稿日期：2015—06—25

*基金項目：國家自然科學基金資助項目(61262081)

中圖分類號:TP 212

文獻標識碼:A

文章編號:1000—9787(2016)03—0133—04

作者簡介:

黃祺(1990-)，男，安徽馬鞍山人，碩士研究生，主要從事無線傳感器網匯聚節(jié)點移動策略的研究。