基于蜂窩網格的變步長移動節點部署算法*

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

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

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

?

基于蜂窩網格的變步長移動節點部署算法*

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

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

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

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

關鍵詞:無線傳感器網絡；節點部署；蜂窩網格

引言

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

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

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

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

1問題陳述

1.1相關假設

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

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

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

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

④ 節點的初始部署是隨機的；

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

⑥數據傳輸過程中的延時等誤差忽略不計。

1.2感知模型

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

1.3評價方法

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

(1) 覆蓋率

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

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

(2) 平均移動距離

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

(3) 部署時間

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

2本文算法

2.1基本網格劃分結構

圖1　監測區域的基本網格結構

2.2基于蜂窩網格的變步長部署策略

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

(1) 節點移動目標選擇

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

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

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

② 如果i

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

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

圖2　節點與其目標網格坐標方位圖

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

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

圖3　節點與其目標網格之間的包含關系

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

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

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

圖4　對節點與其目標網格中心距離的數學統計

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

經過以上分析，可以得到以下的部署策略：

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

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

圖5　部署處于其目標網格點外部節點的路徑選擇

3仿真結果

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

表1　傳感器節點的相關參數

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

圖6　監測區域在不同算法下得到的覆蓋率

圖7　節點的平均移動距離

結語

[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] 周浦城,崔遜學,王書敏,等.基于虛擬力的無線傳感器網絡覆蓋增強算法[J].系統仿真學報,2009(5):1416-1419.

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

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

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

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

[8] 錢開國,王偉,申時凱,等.基于蜂窩網格錨點的虛擬力導向節點部署算法[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