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

(昆明理工大學(xué) 計(jì)算機(jī)重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650504)

?

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

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

(昆明理工大學(xué) 計(jì)算機(jī)重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650504)

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

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò)； 匯聚節(jié)點(diǎn)重定位； 蜂巢虛擬網(wǎng)格； 網(wǎng)絡(luò)壽命

0引言

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

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

基于簇的方法使用了分簇機(jī)制將網(wǎng)絡(luò)分層，并在每層或者每個(gè)網(wǎng)格中使用簇頭作為高層次收集轉(zhuǎn)發(fā)節(jié)點(diǎn)[6]。每個(gè)簇頭加入一個(gè)且只能加入一個(gè)最近的簇，并感知收集其所在簇中的數(shù)據(jù)。相比于網(wǎng)格來(lái)說(shuō)，成簇要更加復(fù)雜困難。然而，由于簇是參照節(jié)點(diǎn)拓?fù)涓兄畔⒔⒌?，虛擬層次結(jié)構(gòu)實(shí)現(xiàn)也尤為有效。

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

基于骨干網(wǎng)的方法中源節(jié)點(diǎn)通過(guò)骨干網(wǎng)來(lái)向匯聚節(jié)點(diǎn)傳輸感知信息[8]。骨干網(wǎng)由網(wǎng)關(guān)節(jié)點(diǎn)和簇節(jié)點(diǎn)組成。骨干網(wǎng)較為適用于延遲容忍網(wǎng)絡(luò)，因?yàn)橹挥挟?dāng)匯聚節(jié)點(diǎn)靠近所選擇的網(wǎng)關(guān)時(shí)會(huì)傳輸聚合數(shù)據(jù)。

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

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

1HEESR策略

1.1網(wǎng)格模型

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

圖1　網(wǎng)格模型與移動(dòng)策略Fig 1　Grid model and mobile strategy

1.2HEESR

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

圖2　HEESR流程圖Fig 2　Flowchart of HEESR

依據(jù)判斷所得權(quán)值wmv，Sink選擇移動(dòng)的位置。當(dāng)數(shù)據(jù)信息收集處理完畢，匯聚節(jié)點(diǎn)Sink就會(huì)以一個(gè)恒定的速度向選擇的網(wǎng)格中心移動(dòng)。當(dāng)Sink到達(dá)預(yù)定位置，整個(gè)網(wǎng)絡(luò)中的拓?fù)渚蜁?huì)依據(jù)Sink的當(dāng)前位置產(chǎn)生變化。Sink會(huì)在當(dāng)前位置停留一定時(shí)間來(lái)實(shí)時(shí)地收集數(shù)據(jù)信息。依據(jù)網(wǎng)絡(luò)中能量變化，匯聚節(jié)點(diǎn)Sink重定位的過(guò)程會(huì)一直持續(xù)下去，直至網(wǎng)絡(luò)中第一個(gè)節(jié)點(diǎn)死亡。

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

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

1.3傳輸半徑調(diào)整機(jī)制

2性能分析

2.1能耗模型

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

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

(1)

當(dāng)節(jié)點(diǎn)q接收p發(fā)送的消息時(shí)，則用式(2)來(lái)計(jì)算能耗

Er(k,d)=Eelec·k,

(2)

在上述公式中Eelec為由所述傳感器節(jié)點(diǎn)收發(fā)電路時(shí)所消耗的能量。Eamp為由放大器所消耗的能量。因?yàn)樗袀鞲衅鞴?jié)點(diǎn)位置保持不變，所以,節(jié)點(diǎn)p向節(jié)點(diǎn)q傳輸k字節(jié)產(chǎn)生的能耗與節(jié)點(diǎn)q向節(jié)點(diǎn)p傳輸k字節(jié)產(chǎn)生的能耗相等。

2.2參數(shù)設(shè)置

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

表1　默認(rèn)實(shí)驗(yàn)參數(shù)

圖4　節(jié)點(diǎn)數(shù)目對(duì)網(wǎng)絡(luò)壽命的影響Fig 4　Effect of number of nodes on network lifetime

圖5　節(jié)點(diǎn)初始能量對(duì)網(wǎng)絡(luò)壽命的影響Fig 5　Effect of initial energy on network lifetime

圖6　傳輸半徑對(duì)網(wǎng)絡(luò)壽命影響Fig 6　Effect of transmission radius on network lifetime

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

3結(jié)論

本文提出了HEESR策略,基于鄰居網(wǎng)格中節(jié)點(diǎn)的剩余能耗和網(wǎng)格的平均剩余能量，匯聚節(jié)點(diǎn)可以向周邊六個(gè)網(wǎng)格進(jìn)行移動(dòng)。仿真實(shí)驗(yàn)表明：HEESR策略能夠有效降低傳感器節(jié)點(diǎn)的傳輸負(fù)載和能耗，達(dá)到更長(zhǎng)的網(wǎng)絡(luò)壽命。在接下來(lái)的研究中，會(huì)考慮當(dāng)節(jié)點(diǎn)平均能量下降到預(yù)定閾值時(shí)，調(diào)整網(wǎng)絡(luò)虛擬網(wǎng)格大小和采用多匯聚節(jié)點(diǎn)數(shù)目時(shí)的匯聚節(jié)點(diǎn)重定位策略。

參考文獻(xiàn):

[1]吳曉培,吳躍,陳湘.密集傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)隨機(jī)調(diào)度算法研究[J].電子科技大學(xué)學(xué)報(bào),2010,39(1):119-122.

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

[3]吳小兵,陳貴海.無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)非均勻分布的能量空洞問(wèn)題[J].計(jì)算機(jī)學(xué)報(bào)，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é)能的傳感器網(wǎng)絡(luò)數(shù)據(jù)收集和聚合協(xié)議[J].軟件學(xué)報(bào)，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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61262081)

中圖分類號(hào):TP 212

文獻(xiàn)標(biāo)識(shí)碼:A

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

作者簡(jiǎn)介:

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