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

朱明，金仁成，車志平，李應(yīng)琛

(大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，大連 116024)

* 基金項(xiàng)目：國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)資助項(xiàng)目(2009CB320300)；國(guó)家“十二五”科技支撐計(jì)劃資助項(xiàng)目(2011BAG05B02)。

?

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

朱明，金仁成，車志平，李應(yīng)琛

(大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，大連 116024)

* 基金項(xiàng)目：國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃(973計(jì)劃)資助項(xiàng)目(2009CB320300)；國(guó)家“十二五”科技支撐計(jì)劃資助項(xiàng)目(2011BAG05B02)。

摘要:針對(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%以上的覆蓋率。

關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)部署；蜂窩網(wǎng)格

引言

無(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)[2-4]。節(jié)點(diǎn)受監(jiān)測(cè)區(qū)域內(nèi)其他節(jié)點(diǎn)的虛擬引力和斥力的作用而移動(dòng)，合力為0時(shí)，停止移動(dòng)?；谔摂M力的算法能夠有效提高監(jiān)測(cè)區(qū)域覆蓋率，但因?yàn)楣?jié)點(diǎn)沒(méi)有移動(dòng)目標(biāo)，容易形成監(jiān)測(cè)空洞。

參考文獻(xiàn)另一種就是借助網(wǎng)格劃分的策略，從節(jié)點(diǎn)的覆蓋效率出發(fā)，實(shí)現(xiàn)監(jiān)測(cè)區(qū)域的節(jié)點(diǎn)部署。[5]首次提出當(dāng)且僅當(dāng)3個(gè)半徑為1的圓交于一點(diǎn)，且三個(gè)圓心連成邊長(zhǎng)為的等邊三角形時(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)格劃分的虛擬力部署算法，但是，該算法沒(méi)有在全局上從最短距離開(kāi)始尋找，會(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)模型。 利用[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%。

針對(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感知模型

為簡(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)

圖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)開(kāi)始。

(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

圖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所列。

表1　傳感器節(jié)點(diǎn)的相關(guān)參數(shù)

在基于蜂窩網(wǎng)格的節(jié)點(diǎn)部署策略的仿真試驗(yàn)中，首先開(kāi)始移動(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ǔ)

[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] 周浦城,崔遜學(xué),王書(shū)敏,等.基于虛擬力的無(wú)線傳感器網(wǎng)絡(luò)覆蓋增強(qiáng)算法[J].系統(tǒng)仿真學(xué)報(bào),2009(5):1416-1419.

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

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

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

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

[8] 錢開(kāi)國(guó),王偉,申時(shí)凱,等.基于蜂窩網(wǎng)格錨點(diǎn)的虛擬力導(dǎo)向節(jié)點(diǎn)部署算法[J].計(jì)算機(jī)測(cè)量與控制,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.

(責(zé)任編輯：薛士然收修改稿日期：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

中圖分類號(hào):TP393.17

文獻(xiàn)標(biāo)識(shí)碼:A