基于蜂窩網(wǎng)格的變步長移動節(jié)點(diǎn)部署算法
作者：朱明，金仁成，車志平，李應(yīng)琛 大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室
摘要: 針對無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署問題，提出了一種基于蜂窩網(wǎng)格的變步長節(jié)點(diǎn)部署算法。將監(jiān)測區(qū)域進(jìn)行正六邊形網(wǎng)格劃分，利用網(wǎng)格中心位置信息，以及隨機(jī)散布的節(jié)點(diǎn)的位置信息，每個節(jié)點(diǎn)會找到自己的目標(biāo)網(wǎng)格，目標(biāo)網(wǎng)格中心即為該節(jié)點(diǎn)部署位置。根據(jù)待部署節(jié)點(diǎn)與相應(yīng)目標(biāo)網(wǎng)格頂點(diǎn)之間的距離信息，控制節(jié)點(diǎn)的移動距離。仿真結(jié)果表明，該算法收斂速度快，能以較小的節(jié)點(diǎn)平均移動距離獲得98%以上的覆蓋率。
引言
無線傳感器網(wǎng)絡(luò)(WSN)節(jié)點(diǎn)部署，是在指定的監(jiān)測區(qū)域內(nèi)，適當(dāng)布置傳感器節(jié)點(diǎn)以滿足特定需求，傳感器節(jié)點(diǎn)布置的好壞直接影響WSN所能提供的“感知”服務(wù)質(zhì)量[1]。
一種能夠有效控制節(jié)點(diǎn)的移動策略是借助虛擬力原理導(dǎo)向控制節(jié)點(diǎn)移動[24]。節(jié)點(diǎn)受監(jiān)測區(qū)域內(nèi)其他節(jié)點(diǎn)的虛擬引力和斥力的作用而移動，合力為0時，停止移動；谔摂M力的算法能夠有效提高監(jiān)測區(qū)域覆蓋率，但因?yàn)楣?jié)點(diǎn)沒有移動目標(biāo)，容易形成監(jiān)測空洞。
另一種就是借助網(wǎng)格劃分的策略，從節(jié)點(diǎn)的覆蓋效率出發(fā)，實(shí)現(xiàn)監(jiān)測區(qū)域的節(jié)點(diǎn)部署。參考文獻(xiàn)[5]首次提出當(dāng)且僅當(dāng)3個半徑為1的圓交于一點(diǎn)，且三個圓心連成邊長為3的等邊三角形時，可以獲得最大的覆蓋效率。參考文獻(xiàn)[6]在最大覆蓋效率的基礎(chǔ)上，提出了基于蜂窩網(wǎng)格的傳感器節(jié)點(diǎn)靜態(tài)部署算法，將無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署在組成蜂窩網(wǎng)格的各個六邊形的中心。參考文獻(xiàn)[7]將網(wǎng)格劃分與虛擬力算法有機(jī)結(jié)合，提出了一種基于網(wǎng)格劃分的虛擬力部署算法，但是，該算法沒有在全局上從最短距離開始尋找，會出現(xiàn)能耗過多的情況。參考文獻(xiàn)[8]利用滿足全覆蓋條件的正六邊形蜂窩網(wǎng)絡(luò)拓?fù)淠Ｐ停瑢⒈O(jiān)測區(qū)域劃分成正六邊形的網(wǎng)格結(jié)構(gòu)，在正六邊形的中心設(shè)置虛擬錨節(jié)點(diǎn)，結(jié)合傳統(tǒng)的虛擬力算法，考慮虛擬錨節(jié)點(diǎn)的引力作用，同時兼顧不同移動節(jié)點(diǎn)間的斥力影響，在滿足一定覆蓋率要求的前提下,建立節(jié)點(diǎn)在合力作用下的移動到虛擬錨節(jié)點(diǎn)的運(yùn)動模型。
針對傳統(tǒng)基于虛擬力的移動策略移動目標(biāo)不明確、能耗過大，以及容易出現(xiàn)監(jiān)測漏洞等缺點(diǎn)，提出了一種基于蜂窩網(wǎng)格的變步長節(jié)點(diǎn)部署算法。利用監(jiān)測區(qū)域的正六邊形網(wǎng)格劃分信息，以及隨機(jī)散布的節(jié)點(diǎn)位置信息，每個節(jié)點(diǎn)會找到自己的目標(biāo)網(wǎng)格。根據(jù)待部署節(jié)點(diǎn)與相應(yīng)目標(biāo)網(wǎng)格中心之間的距離信息，控制節(jié)點(diǎn)的移動距離和方向。
1問題陳述
1.1相關(guān)假設(shè)
針對本文的研究，做出以下假設(shè)：
① 所有的傳感器節(jié)點(diǎn)具有相同的感知、通信、計(jì)算以及移動能力；
② 所有的傳感器節(jié)點(diǎn)的感知范圍和通信范圍都是理想的圓形；
③ 所有節(jié)點(diǎn)都能通過GPS等方法獲取自身位置信息，另外，當(dāng)監(jiān)測區(qū)域劃分為蜂窩網(wǎng)狀結(jié)構(gòu)時，每個正六邊形網(wǎng)格的中心坐標(biāo)信息是可以獲取的；
④ 節(jié)點(diǎn)的初始部署是隨機(jī)的；
⑤ 傳感器節(jié)點(diǎn)的通信半徑Rc是其感知半徑Rs的2倍，此時，覆蓋可保證連通[9]；
⑥數(shù)據(jù)傳輸過程中的延時等誤差忽略不計(jì)。
1.2感知模型
假設(shè)傳感器節(jié)點(diǎn)si部署在點(diǎn)xi,yi，對于任意一點(diǎn)P，其坐標(biāo)為x,y，則si與P之間的歐式距離為：
為簡化問題研究，選擇傳感器節(jié)點(diǎn)的模型為二元感知模型。當(dāng)點(diǎn)si與P之間的距離在節(jié)點(diǎn)的感知范圍內(nèi)時，節(jié)點(diǎn)能采集到P點(diǎn)信息的概率為1；當(dāng)點(diǎn)si與P之間的距離在節(jié)點(diǎn)的感知范圍外時，節(jié)點(diǎn)能采集到P點(diǎn)信息的概率為0，如下所示：
1.3評價方法
為了評價算法的優(yōu)劣，引入3個評價機(jī)制：覆蓋率、平均移動距離、部署時間。
(1) 覆蓋率
覆蓋率是評價一個部署策略最重要的指標(biāo),它從直觀上表達(dá)了一個部署策略的好壞。對一些特殊的監(jiān)測區(qū)，需要很高的覆蓋率，同時還要避免出現(xiàn)監(jiān)測空洞。覆蓋率越大，節(jié)點(diǎn)對監(jiān)測區(qū)域的監(jiān)測效果越明顯，部署策略的優(yōu)越性越強(qiáng)。在數(shù)學(xué)上，覆蓋率是所有節(jié)點(diǎn)覆蓋區(qū)域面積的并集與監(jiān)測區(qū)域面積的比值，如下所示：
式中，Ai是每個節(jié)點(diǎn)的覆蓋面積，A是監(jiān)測區(qū)域的面積，Coverage(%)是監(jiān)測區(qū)域的覆蓋率。
（2) 平均移動距離
平均移動距離體現(xiàn)了每個節(jié)點(diǎn)在部署過程中移動距離的多少。由于節(jié)點(diǎn)在移動過程中需要消耗能量，平均移動距離也間接反映節(jié)點(diǎn)在部署過程中消耗能量的平均水平。平均移動距離越小，節(jié)點(diǎn)的平均能耗越低。當(dāng)節(jié)點(diǎn)部署策略實(shí)施完成，可以利用式(4)來計(jì)算節(jié)點(diǎn)的平均移動距離。
(3) 部署時間
在對時間要求嚴(yán)格的場合,部署時間是非常重要的指標(biāo)。在本文中，部署時間定義為從初始節(jié)點(diǎn)隨機(jī)散布到所有節(jié)點(diǎn)部署完成的這段時間。部署時間的長短與部署策略的關(guān)系很大，它能反映一個部署策略的好壞。
2本文算法
2.1基本網(wǎng)格劃分結(jié)構(gòu)
利用參考文獻(xiàn)[5-6]中提到的部署模型，對監(jiān)測區(qū)域進(jìn)行網(wǎng)格劃分，得到如圖1所示的蜂窩網(wǎng)絡(luò)結(jié)構(gòu)，這樣就很容易得到蜂窩網(wǎng)絡(luò)中每個正六邊形網(wǎng)格的中心坐標(biāo)。圖中正六邊形網(wǎng)格的邊長為節(jié)點(diǎn)的感知半徑，當(dāng)節(jié)點(diǎn)處于各個網(wǎng)格的中心時，即為參考文獻(xiàn)[6]所述的靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)，傳感器節(jié)點(diǎn)的覆蓋效率最高，達(dá)到82.7%。
圖1 監(jiān)測區(qū)域的基本網(wǎng)格結(jié)構(gòu)
2.2基于蜂窩網(wǎng)格的變步長部署策略
按照圖1所示的基本網(wǎng)狀結(jié)構(gòu)，將各個正六邊形網(wǎng)格的中心作為隨機(jī)散布的移動傳感器節(jié)點(diǎn)的移動目標(biāo)。當(dāng)節(jié)點(diǎn)隨機(jī)散布后，根據(jù)最小距離原則在全局上分配每個傳感器節(jié)點(diǎn)的目標(biāo)網(wǎng)格，當(dāng)所有節(jié)點(diǎn)選擇目標(biāo)網(wǎng)格點(diǎn)之后，節(jié)點(diǎn)移動開始。
(1) 節(jié)點(diǎn)移動目標(biāo)選擇
當(dāng)傳感器節(jié)點(diǎn)隨機(jī)散布后，利用節(jié)點(diǎn)位置信息、正六邊形網(wǎng)格中心坐標(biāo)信息，可以計(jì)算出每個傳感器節(jié)點(diǎn)與圖1中任意一個正六邊形網(wǎng)格中心之間的距離信息，將其記作一個m×n的矩陣Dm,n，如下所示：
式中，m是隨機(jī)散布的傳感器節(jié)點(diǎn)的個數(shù)，n是監(jiān)測區(qū)域劃分得到的正六邊形網(wǎng)格的個數(shù)，矩陣中的每一行元素代表傳感器節(jié)點(diǎn)i到n個正六邊形網(wǎng)格之間的距離。對矩陣中的元素進(jìn)行查找，確定每個傳感器節(jié)點(diǎn)的目標(biāo)網(wǎng)格，處理過程如下：
① 對距離矩陣中的所有元素進(jìn)行第一輪查找，找到其中最小的元素dij，由此確定第i個節(jié)點(diǎn)的目標(biāo)網(wǎng)格為網(wǎng)格j，并標(biāo)記節(jié)點(diǎn)i已確定為目標(biāo)網(wǎng)格，第i行和第j列的所有元素不參與下次查找;
② 如果i③ 節(jié)點(diǎn)的移動目標(biāo)選擇完成，查找過程結(jié)束。
(2) 確定節(jié)點(diǎn)移動方向α及每次移動距離Mov_D
當(dāng)所有傳感器節(jié)點(diǎn)找到自己的目標(biāo)網(wǎng)格后，節(jié)點(diǎn)的移動策略開始執(zhí)行。由節(jié)點(diǎn)與目標(biāo)網(wǎng)格中心之間的位置關(guān)系,可以確定節(jié)點(diǎn)移動的方向。假設(shè)節(jié)點(diǎn)si的坐標(biāo)為xi,yi，其目標(biāo)網(wǎng)格中心的坐標(biāo)為xc,yc，如圖2所示。
圖2 節(jié)點(diǎn)與其目標(biāo)網(wǎng)格坐標(biāo)方位圖
顯然，由二者的坐標(biāo)信息可以計(jì)算出節(jié)點(diǎn)的移動方向角α，如下所示：
為了得到比較完善的部署控制策略，需要研究傳感器節(jié)點(diǎn)在部署過程中移動距離的選擇。如圖3所示，方格代表的是正六邊形的頂點(diǎn)，方格內(nèi)部的數(shù)字是頂點(diǎn)的編號，圓圈代表的是傳感器網(wǎng)絡(luò)節(jié)點(diǎn)。顯然，傳感器節(jié)點(diǎn)與目標(biāo)網(wǎng)格的位置關(guān)系不確定，既可在網(wǎng)格內(nèi)部，也可在網(wǎng)格外部。若節(jié)點(diǎn)與目標(biāo)網(wǎng)格中心的距離大于最大移動步長，則需要先對節(jié)點(diǎn)以最大步長進(jìn)行移動，直到節(jié)點(diǎn)與目標(biāo)網(wǎng)格中心的距離小于最大移動步長，則以當(dāng)前距離為移動步長；若節(jié)點(diǎn)與目標(biāo)網(wǎng)格中心的距離小于最大移動步長時，以當(dāng)前距離作為節(jié)點(diǎn)的移動步長。以d表示節(jié)點(diǎn)與其目標(biāo)網(wǎng)格點(diǎn)之間的距離，Max_Step為最大移動步長，Mov_D為每次移動距離，則每次移動距離的選擇如下所示：
圖3 節(jié)點(diǎn)與其目標(biāo)網(wǎng)格之間的包含關(guān)系
(3) 考慮避障問題的部署策略研究
在節(jié)點(diǎn)的部署過程中，節(jié)點(diǎn)之間相互碰撞的可能性不可忽略,特別在基于移動機(jī)器人的節(jié)點(diǎn)部署場合，當(dāng)初始部署階段具有很高的速度時，節(jié)點(diǎn)間的相互碰撞會造成節(jié)點(diǎn)不可修復(fù)的損壞。因此，對節(jié)點(diǎn)避障策略的研究是非常有必要的。
針對節(jié)點(diǎn)之間會產(chǎn)生碰撞的問題，提出了一種基于接替移動法的避障策略。為了更好地說明該避障策略，先對節(jié)點(diǎn)與其目標(biāo)網(wǎng)格之間的距離進(jìn)行數(shù)學(xué)統(tǒng)計(jì)，如圖4所示。
圖4 對節(jié)點(diǎn)與其目標(biāo)網(wǎng)格中心距離的數(shù)學(xué)統(tǒng)計(jì)
經(jīng)過統(tǒng)計(jì)發(fā)現(xiàn)，67%的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的移動距離小于或等于4，即位于其目標(biāo)網(wǎng)格內(nèi)部。顯然，由于是從全局上進(jìn)行目標(biāo)網(wǎng)格查找，該節(jié)點(diǎn)與相應(yīng)的目標(biāo)網(wǎng)格中心之間不會再有其他的傳感器節(jié)點(diǎn)，否則該網(wǎng)格并不是該節(jié)點(diǎn)對應(yīng)的目標(biāo)網(wǎng)格。
經(jīng)過以上分析，可以得到以下的部署策略：
① 部署處于其目標(biāo)網(wǎng)格內(nèi)的節(jié)點(diǎn)，一次移動到達(dá)相應(yīng)的目標(biāo)網(wǎng)格中心，這類節(jié)點(diǎn)部署完畢。
② 部署節(jié)點(diǎn)處于其目標(biāo)網(wǎng)格外部的節(jié)點(diǎn)，如圖5所示，首先查找節(jié)點(diǎn)S與其目標(biāo)網(wǎng)格G之間的一系列已經(jīng)部署的節(jié)點(diǎn)A、B、C…，以這些節(jié)點(diǎn)為基礎(chǔ)，優(yōu)先選擇之前移動距離較小的節(jié)點(diǎn)建立移動路徑，將節(jié)點(diǎn)S向目標(biāo)網(wǎng)格G的移動轉(zhuǎn)化為C→G，B→C，A→B，S→A的移動過程，在整個移動過程中，節(jié)點(diǎn)的每次移動先以最大移動步長Mov_Step移動，直到與目標(biāo)網(wǎng)格中心的距離小于最大移動步長時，再以當(dāng)前距離作為節(jié)點(diǎn)的移動步長。
圖5 部署處于其目標(biāo)網(wǎng)格點(diǎn)外部節(jié)點(diǎn)的路徑選擇
3仿真結(jié)果
為了驗(yàn)證算法的優(yōu)越性，借助Matlab對上述算法進(jìn)行仿真試驗(yàn)。在試驗(yàn)中，設(shè)定傳感器節(jié)點(diǎn)的相關(guān)參數(shù)如表1所列。
在基于蜂窩網(wǎng)格的節(jié)點(diǎn)部署策略的仿真試驗(yàn)中，首先開始移動的是處于目標(biāo)網(wǎng)格內(nèi)部的節(jié)點(diǎn)，一次移動達(dá)到目標(biāo)網(wǎng)格中心；接著運(yùn)用考慮避障的部署策略移動處于目標(biāo)網(wǎng)格外部的傳感器節(jié)點(diǎn)。從圖6可以看出，基于蜂窩網(wǎng)格的部署算法獲得的覆蓋率，在第一次部署得到的覆蓋率低于虛擬力算法得到的覆蓋率，但是在第4次循環(huán)迭代以后有明顯增加的趨勢，在第7次循環(huán)迭代后覆蓋率達(dá)到95%以上，明顯高于虛擬力算法獲得的最高90%左右的覆蓋率。更重要的是，從圖7中可以看出，基于蜂窩網(wǎng)格策略的部署算法中，節(jié)點(diǎn)的最大平均移動距離為6 m，相比虛擬力算法中的8 m有所減小。
圖6 監(jiān)測區(qū)域在不同算法下得到的覆蓋率
圖7 節(jié)點(diǎn)的平均移動距離
結(jié)語
本文實(shí)現(xiàn)了基于蜂窩網(wǎng)格的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)部署策略，相比傳統(tǒng)的虛擬力算法，在提高覆蓋率的同時，降低了節(jié)點(diǎn)的平均能耗。Matlab仿真實(shí)驗(yàn)表明，本文提出的算法能使覆蓋率提高12%，節(jié)點(diǎn)平均移動距離減小25%，這從直觀上反映出基于蜂窩網(wǎng)格策略的部署算法能節(jié)省能量。
編輯：admin 最后修改時間：2017-09-05
