基于蜂窩網(wǎng)格的變步長移動節(jié)點部署算法
作者：朱明，金仁成，車志平，李應琛 大連理工大學 遼寧省微納米技術及系統(tǒng)工程重點實驗室
摘要: 針對無線傳感器網(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)絡(WSN)節(jié)點部署，是在指定的監(jiān)測區(qū)域內(nèi)，適當布置傳感器節(jié)點以滿足特定需求，傳感器節(jié)點布置的好壞直接影響WSN所能提供的“感知”服務質量[1]。
一種能夠有效控制節(jié)點的移動策略是借助虛擬力原理導向控制節(jié)點移動[24]。節(jié)點受監(jiān)測區(qū)域內(nèi)其他節(jié)點的虛擬引力和斥力的作用而移動，合力為0時，停止移動；谔摂M力的算法能夠有效提高監(jiān)測區(qū)域覆蓋率，但因為節(jié)點沒有移動目標，容易形成監(jiān)測空洞。
另一種就是借助網(wǎng)格劃分的策略，從節(jié)點的覆蓋效率出發(fā)，實現(xiàn)監(jiān)測區(qū)域的節(jié)點部署。參考文獻[5]首次提出當且僅當3個半徑為1的圓交于一點，且三個圓心連成邊長為3的等邊三角形時，可以獲得最大的覆蓋效率。參考文獻[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é)點的運動模型。
針對傳統(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部署在點xi,yi，對于任意一點P，其坐標為x,y，則si與P之間的歐式距離為：
為簡化問題研究，選擇傳感器節(jié)點的模型為二元感知模型。當點si與P之間的距離在節(jié)點的感知范圍內(nèi)時，節(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)格劃分結構
利用參考文獻[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%。
圖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
當所有傳感器節(jié)點找到自己的目標網(wǎng)格后，節(jié)點的移動策略開始執(zhí)行。由節(jié)點與目標網(wǎng)格中心之間的位置關系,可以確定節(jié)點移動的方向。假設節(jié)點si的坐標為xi,yi，其目標網(wǎng)格中心的坐標為xc,yc，如圖2所示。
圖2 節(jié)點與其目標網(wǎng)格坐標方位圖
顯然，由二者的坐標信息可以計算出節(jié)點的移動方向角α，如下所示：
為了得到比較完善的部署控制策略，需要研究傳感器節(jié)點在部署過程中移動距離的選擇。如圖3所示，方格代表的是正六邊形的頂點，方格內(nèi)部的數(shù)字是頂點的編號，圓圈代表的是傳感器網(wǎng)絡節(jié)點。顯然，傳感器節(jié)點與目標網(wǎng)格的位置關系不確定，既可在網(wǎng)格內(nèi)部，也可在網(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)格內(nèi)部。顯然，由于是從全局上進行目標網(wǎng)格查找，該節(jié)點與相應的目標網(wǎng)格中心之間不會再有其他的傳感器節(jié)點，否則該網(wǎng)格并不是該節(jié)點對應的目標網(wǎng)格。
經(jīng)過以上分析，可以得到以下的部署策略：
① 部署處于其目標網(wǎng)格內(nèi)的節(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所列。
在基于蜂窩網(wǎng)格的節(jié)點部署策略的仿真試驗中，首先開始移動的是處于目標網(wǎng)格內(nèi)部的節(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é)點的平均移動距離
結語
本文實現(xiàn)了基于蜂窩網(wǎng)格的無線傳感器網(wǎng)絡節(jié)點部署策略，相比傳統(tǒng)的虛擬力算法，在提高覆蓋率的同時，降低了節(jié)點的平均能耗。Matlab仿真實驗表明，本文提出的算法能使覆蓋率提高12%，節(jié)點平均移動距離減小25%，這從直觀上反映出基于蜂窩網(wǎng)格策略的部署算法能節(jié)省能量。
編輯：admin 最后修改時間：2017-09-05
