朱明，金仁成，車志平，李應琛

(大連理工大學 遼寧省微納米技術及系統(tǒng)工程重點實驗室，大連 116024)

* 基金項目：國家重點基礎研究發(fā)展計劃(973計劃)資助項目(2009CB320300)；國家“十二五”科技支撐計劃資助項目(2011BAG05B02)。

?

基于蜂窩網(wǎng)格的變步長移動節(jié)點部署算法*

朱明，金仁成，車志平，李應琛

(大連理工大學 遼寧省微納米技術及系統(tǒng)工程重點實驗室，大連 116024)

* 基金項目：國家重點基礎研究發(fā)展計劃(973計劃)資助項目(2009CB320300)；國家“十二五”科技支撐計劃資助項目(2011BAG05B02)。

摘要:針對無線傳感器網(wǎng)絡節(jié)點部署問題，提出了一種基于蜂窩網(wǎng)格的變步長節(jié)點部署算法。將監(jiān)測區(qū)域進行正六邊形網(wǎng)格劃分，利用網(wǎng)格中心位置信息，以及隨機散布的節(jié)點的位置信息，每個節(jié)點會找到自己的目標網(wǎng)格，目標網(wǎng)格中心即為該節(jié)點部署位置。根據(jù)待部署節(jié)點與相應目標網(wǎng)格頂點之間的距離信息，控制節(jié)點的移動距離。仿真結果表明，該算法收斂速度快，能以較小的節(jié)點平均移動距離獲得98%以上的覆蓋率。

關鍵詞:無線傳感器網(wǎng)絡；節(jié)點部署；蜂窩網(wǎng)格

引言

無線傳感器網(wǎng)絡(WSN)節(jié)點部署，是在指定的監(jiān)測區(qū)域內，適當布置傳感器節(jié)點以滿足特定需求，傳感器節(jié)點布置的好壞直接影響WSN所能提供的“感知”服務質量[1]。

一種能夠有效控制節(jié)點的移動策略是借助虛擬力原理導向控制節(jié)點移動[2-4]。節(jié)點受監(jiān)測區(qū)域內其他節(jié)點的虛擬引力和斥力的作用而移動，合力為0時，停止移動。基于虛擬力的算法能夠有效提高監(jiān)測區(qū)域覆蓋率，但因為節(jié)點沒有移動目標，容易形成監(jiān)測空洞。

參考文獻另一種就是借助網(wǎng)格劃分的策略，從節(jié)點的覆蓋效率出發(fā)，實現(xiàn)監(jiān)測區(qū)域的節(jié)點部署。[5]首次提出當且僅當3個半徑為1的圓交于一點，且三個圓心連成邊長為的等邊三角形時，可以獲得最大的覆蓋效率。參考文獻[6]在最大覆蓋效率的基礎上，提出了基于蜂窩網(wǎng)格的傳感器節(jié)點靜態(tài)部署算法，將無線傳感器網(wǎng)絡節(jié)點部署在組成蜂窩網(wǎng)格的各個六邊形的中心。參考文獻[7]將網(wǎng)格劃分與虛擬力算法有機結合，提出了一種基于網(wǎng)格劃分的虛擬力部署算法，但是，該算法沒有在全局上從最短距離開始尋找，會出現(xiàn)能耗過多的情況。參考文獻[8]利用滿足全覆蓋條件的正六邊形蜂窩網(wǎng)絡拓撲模型，將監(jiān)測區(qū)域劃分成正六邊形的網(wǎng)格結構，在正六邊形的中心設置虛擬錨節(jié)點，結合傳統(tǒng)的虛擬力算法，考慮虛擬錨節(jié)點的引力作用，同時兼顧不同移動節(jié)點間的斥力影響，在滿足一定覆蓋率要求的前提下,建立節(jié)點在合力作用下的移動到虛擬錨節(jié)點的運動模型。 利用[5-6]中提到的部署模型，對監(jiān)測區(qū)域進行網(wǎng)格劃分，得到如圖1所示的蜂窩網(wǎng)絡結構，這樣就很容易得到蜂窩網(wǎng)絡中每個正六邊形網(wǎng)格的中心坐標。圖中正六邊形網(wǎng)格的邊長為節(jié)點的感知半徑，當節(jié)點處于各個網(wǎng)格的中心時，即為參考文獻[6]所述的靜態(tài)網(wǎng)絡結構，傳感器節(jié)點的覆蓋效率最高，達到82.7%。

針對傳統(tǒng)基于虛擬力的移動策略移動目標不明確、能耗過大，以及容易出現(xiàn)監(jiān)測漏洞等缺點，提出了一種基于蜂窩網(wǎng)格的變步長節(jié)點部署算法。利用監(jiān)測區(qū)域的正六邊形網(wǎng)格劃分信息，以及隨機散布的節(jié)點位置信息，每個節(jié)點會找到自己的目標網(wǎng)格。根據(jù)待部署節(jié)點與相應目標網(wǎng)格中心之間的距離信息，控制節(jié)點的移動距離和方向。

1問題陳述

1.1相關假設

針對本文的研究，做出以下假設：

① 所有的傳感器節(jié)點具有相同的感知、通信、計算以及移動能力；

② 所有的傳感器節(jié)點的感知范圍和通信范圍都是理想的圓形；

③ 所有節(jié)點都能通過GPS等方法獲取自身位置信息，另外，當監(jiān)測區(qū)域劃分為蜂窩網(wǎng)狀結構時，每個正六邊形網(wǎng)格的中心坐標信息是可以獲取的；

④ 節(jié)點的初始部署是隨機的；

⑤ 傳感器節(jié)點的通信半徑Rc是其感知半徑Rs的2倍，此時，覆蓋可保證連通[9]；

⑥數(shù)據(jù)傳輸過程中的延時等誤差忽略不計。

1.2感知模型

為簡化問題研究，選擇傳感器節(jié)點的模型為二元感知模型。當點si與P之間的距離在節(jié)點的感知范圍內時，節(jié)點能采集到P點信息的概率為1；當點si與P之間的距離在節(jié)點的感知范圍外時，節(jié)點能采集到P點信息的概率為0，如下所示：

1.3評價方法

為了評價算法的優(yōu)劣，引入3個評價機制：覆蓋率、平均移動距離、部署時間。

(1) 覆蓋率

覆蓋率是評價一個部署策略最重要的指標,它從直觀上表達了一個部署策略的好壞。對一些特殊的監(jiān)測區(qū)，需要很高的覆蓋率，同時還要避免出現(xiàn)監(jiān)測空洞。覆蓋率越大，節(jié)點對監(jiān)測區(qū)域的監(jiān)測效果越明顯，部署策略的優(yōu)越性越強。在數(shù)學上，覆蓋率是所有節(jié)點覆蓋區(qū)域面積的并集與監(jiān)測區(qū)域面積的比值，如下所示：

式中，Ai是每個節(jié)點的覆蓋面積，A是監(jiān)測區(qū)域的面積，Coverage(%)是監(jiān)測區(qū)域的覆蓋率。

(2) 平均移動距離

平均移動距離體現(xiàn)了每個節(jié)點在部署過程中移動距離的多少。由于節(jié)點在移動過程中需要消耗能量，平均移動距離也間接反映節(jié)點在部署過程中消耗能量的平均水平。平均移動距離越小，節(jié)點的平均能耗越低。當節(jié)點部署策略實施完成，可以利用式(4)來計算節(jié)點的平均移動距離。

(3) 部署時間

在對時間要求嚴格的場合,部署時間是非常重要的指標。在本文中，部署時間定義為從初始節(jié)點隨機散布到所有節(jié)點部署完成的這段時間。部署時間的長短與部署策略的關系很大，它能反映一個部署策略的好壞。

2本文算法

2.1基本網(wǎng)格劃分結構

圖1　監(jiān)測區(qū)域的基本網(wǎng)格結構

2.2基于蜂窩網(wǎng)格的變步長部署策略

按照圖1所示的基本網(wǎng)狀結構，將各個正六邊形網(wǎng)格的中心作為隨機散布的移動傳感器節(jié)點的移動目標。當節(jié)點隨機散布后，根據(jù)最小距離原則在全局上分配每個傳感器節(jié)點的目標網(wǎng)格，當所有節(jié)點選擇目標網(wǎng)格點之后，節(jié)點移動開始。

(1) 節(jié)點移動目標選擇

當傳感器節(jié)點隨機散布后，利用節(jié)點位置信息、正六邊形網(wǎng)格中心坐標信息，可以計算出每個傳感器節(jié)點與圖1中任意一個正六邊形網(wǎng)格中心之間的距離信息，將其記作一個m×n的矩陣Dm,n，如下所示：

式中，m是隨機散布的傳感器節(jié)點的個數(shù)，n是監(jiān)測區(qū)域劃分得到的正六邊形網(wǎng)格的個數(shù)，矩陣中的每一行元素代表傳感器節(jié)點i到n個正六邊形網(wǎng)格之間的距離。對矩陣中的元素進行查找，確定每個傳感器節(jié)點的目標網(wǎng)格，處理過程如下：

① 對距離矩陣中的所有元素進行第一輪查找，找到其中最小的元素dij，由此確定第i個節(jié)點的目標網(wǎng)格為網(wǎng)格j，并標記節(jié)點i已確定為目標網(wǎng)格，第i行和第j列的所有元素不參與下次查找;

② 如果i

③ 節(jié)點的移動目標選擇完成，查找過程結束。

(2) 確定節(jié)點移動方向α及每次移動距離Mov_D

圖2　節(jié)點與其目標網(wǎng)格坐標方位圖

顯然，由二者的坐標信息可以計算出節(jié)點的移動方向角α，如下所示：

為了得到比較完善的部署控制策略，需要研究傳感器節(jié)點在部署過程中移動距離的選擇。如圖3所示，方格代表的是正六邊形的頂點，方格內部的數(shù)字是頂點的編號，圓圈代表的是傳感器網(wǎng)絡節(jié)點。顯然，傳感器節(jié)點與目標網(wǎng)格的位置關系不確定，既可在網(wǎng)格內部，也可在網(wǎng)格外部。若節(jié)點與目標網(wǎng)格中心的距離大于最大移動步長，則需要先對節(jié)點以最大步長進行移動，直到節(jié)點與目標網(wǎng)格中心的距離小于最大移動步長，則以當前距離為移動步長；若節(jié)點與目標網(wǎng)格中心的距離小于最大移動步長時，以當前距離作為節(jié)點的移動步長。以d表示節(jié)點與其目標網(wǎng)格點之間的距離，Max_Step為最大移動步長，Mov_D為每次移動距離，則每次移動距離的選擇如下所示：

圖3　節(jié)點與其目標網(wǎng)格之間的包含關系

(3) 考慮避障問題的部署策略研究

在節(jié)點的部署過程中，節(jié)點之間相互碰撞的可能性不可忽略,特別在基于移動機器人的節(jié)點部署場合，當初始部署階段具有很高的速度時，節(jié)點間的相互碰撞會造成節(jié)點不可修復的損壞。因此，對節(jié)點避障策略的研究是非常有必要的。

針對節(jié)點之間會產(chǎn)生碰撞的問題，提出了一種基于接替移動法的避障策略。為了更好地說明該避障策略，先對節(jié)點與其目標網(wǎng)格之間的距離進行數(shù)學統(tǒng)計，如圖4所示。

圖4　對節(jié)點與其目標網(wǎng)格中心距離的數(shù)學統(tǒng)計

經(jīng)過統(tǒng)計發(fā)現(xiàn)，67%的傳感器網(wǎng)絡節(jié)點的移動距離小于或等于4，即位于其目標網(wǎng)格內部。顯然，由于是從全局上進行目標網(wǎng)格查找，該節(jié)點與相應的目標網(wǎng)格中心之間不會再有其他的傳感器節(jié)點，否則該網(wǎng)格并不是該節(jié)點對應的目標網(wǎng)格。

經(jīng)過以上分析，可以得到以下的部署策略：

① 部署處于其目標網(wǎng)格內的節(jié)點，一次移動到達相應的目標網(wǎng)格中心，這類節(jié)點部署完畢。

② 部署節(jié)點處于其目標網(wǎng)格外部的節(jié)點，如圖5所示，首先查找節(jié)點S與其目標網(wǎng)格G之間的一系列已經(jīng)部署的節(jié)點A、B、C…，以這些節(jié)點為基礎，優(yōu)先選擇之前移動距離較小的節(jié)點建立移動路徑，將節(jié)點S向目標網(wǎng)格G的移動轉化為C→G，B→C，A→B，S→A的移動過程，在整個移動過程中，節(jié)點的每次移動先以最大移動步長Mov_Step移動，直到與目標網(wǎng)格中心的距離小于最大移動步長時，再以當前距離作為節(jié)點的移動步長。

圖5　部署處于其目標網(wǎng)格點外部節(jié)點的路徑選擇

3仿真結果

為了驗證算法的優(yōu)越性，借助Matlab對上述算法進行仿真試驗。在試驗中，設定傳感器節(jié)點的相關參數(shù)如表1所列。

表1　傳感器節(jié)點的相關參數(shù)

在基于蜂窩網(wǎng)格的節(jié)點部署策略的仿真試驗中，首先開始移動的是處于目標網(wǎng)格內部的節(jié)點，一次移動達到目標網(wǎng)格中心；接著運用考慮避障的部署策略移動處于目標網(wǎng)格外部的傳感器節(jié)點。從圖6可以看出，基于蜂窩網(wǎng)格的部署算法獲得的覆蓋率，在第一次部署得到的覆蓋率低于虛擬力算法得到的覆蓋率，但是在第4次循環(huán)迭代以后有明顯增加的趨勢，在第7次循環(huán)迭代后覆蓋率達到95%以上，明顯高于虛擬力算法獲得的最高90%左右的覆蓋率。更重要的是，從圖7中可以看出，基于蜂窩網(wǎng)格策略的部署算法中，節(jié)點的最大平均移動距離為6 m，相比虛擬力算法中的8 m有所減小。

圖6　監(jiān)測區(qū)域在不同算法下得到的覆蓋率

圖7　節(jié)點的平均移動距離

結語

[1] Li J H,Yu M.Sensor coverage in wireless ad hoc sensor networks[J].International Journal of Sensor Networks,2007,2(3-4):218-229.

[2] Zou Y,Chakrabarty K.Sensor deployment and target localization based on virtual forces[C]//INFOCOM,2003.

[3] 周浦城,崔遜學,王書敏,等.基于虛擬力的無線傳感器網(wǎng)絡覆蓋增強算法[J].系統(tǒng)仿真學報,2009(5):1416-1419.

[4] 周彤,洪炳.基于虛擬力的混合感知網(wǎng)節(jié)點部署[J].計算機研究與發(fā)展,2015,44(6):965-972.

[5] 曹峰,劉麗萍,王智.能量有效的無線傳感器網(wǎng)絡部署[J].信息與控制,2006,35(2):147-153.

[6] 凡志剛,郭文生,桑楠.一種基于蜂窩網(wǎng)格的傳感器節(jié)點部署算法[J].傳感器與微系統(tǒng),2008(4):15-17.

[7] 李賢,何啟麗,唐秋玲,等.一種基于網(wǎng)格劃分的虛擬力部署算法的研究[J].廣西大學學報:自然科學版,2013,37(6):1164-1169.

[8] 錢開國,王偉,申時凱,等.基于蜂窩網(wǎng)格錨點的虛擬力導向節(jié)點部署算法[J].計算機測量與控制,2014,22(6):1839-1841.

[9] Zhang H,Hou J C.Maintaining sensing coverage and connectivity in large sensor networks[J].Ad Hoc&Sensor Wireless Networks,2005,1(1-2):89-124.

(責任編輯：薛士然收修改稿日期：2015-06-29)

Sensor Deployment Algorithm with Variable Step Size Based on Hexagonal Grid

Zhu Ming,Jin Rencheng,Che Zhiping,Li Yingchen

(Key Laboratory for Micro/Nano Technology and System of Liaoning Province,Dalian University of Technology,Dalian 116024,China)

Abstract：To solve the issue of wireless sensor network deployment,a sensor deployment algorithm with variable step size based on hexagonal grid is proposed.The monitoring field is drawn into regular hexagonal grids.Using the location information of each hexagon’s center and the random deployed sensor nodes,each node’s targeting grid can be found.The node should be deployed at the targeting grid’s center.Based on the distance between the deploying nodes and the targeting grid’s center,the move step can be selected.The simulation results show that the proposed algorithm can achieve a coverage of 98% with a faster convergence speed and a lower average moving distance.

Key words:wireless sensor network;sensor deployment;hexagonal grid

中圖分類號:TP393.17

文獻標識碼:A