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