無線傳感器網(wǎng)絡(luò)覆蓋連通性研究

無線傳感器網(wǎng)絡(luò)一般都是隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)，一旦傳感器節(jié)點(diǎn)分布完畢，網(wǎng)絡(luò)管理者和用戶基本上就很難對(duì)節(jié)點(diǎn)進(jìn)行直接管理。此時(shí)，往往通過智能基站對(duì)具有信息存儲(chǔ)和有限計(jì)算能力和能量的節(jié)點(diǎn)進(jìn)行全局管理。因此，正確獲悉部署區(qū)域內(nèi)傳感器節(jié)點(diǎn)的工作情況是高效、合理地對(duì)網(wǎng)絡(luò)進(jìn)行管理和應(yīng)用的重要前提。首先，使用節(jié)點(diǎn)代理方案對(duì)監(jiān)測(cè)區(qū)域內(nèi)的節(jié)點(diǎn)進(jìn)行處理，設(shè)處理結(jié)果產(chǎn)生n-1個(gè)代理，這樣整個(gè)部署區(qū)域就被劃分成n個(gè)組（包括基站），DBDAFNCJ算法分別對(duì)n個(gè)組進(jìn)行處理，處理每個(gè)組時(shí)都是以基站或代理節(jié)點(diǎn)(注：統(tǒng)稱為組長(zhǎng)節(jié)點(diǎn))為起點(diǎn)，然后獲取相關(guān)存儲(chǔ)信息按照逐跳路由的方式對(duì)某一方向的節(jié)點(diǎn)進(jìn)行探測(cè)，算法中設(shè)置一空集，每次將探測(cè)到的節(jié)點(diǎn)加入空集，直到碰到不可達(dá)情況的節(jié)點(diǎn)，此時(shí)回溯到上一個(gè)節(jié)點(diǎn)繼續(xù)探測(cè)未被訪問的可達(dá)節(jié)點(diǎn)，當(dāng)n個(gè)組都處理完畢以后，每組節(jié)點(diǎn)的并集即是部署區(qū)域內(nèi)可以正常工作的節(jié)點(diǎn)。圖3描述了使用DBDAFNCJ算法探測(cè)各組內(nèi)節(jié)點(diǎn)連通性的方法。

算法DBDAFNCJ
AlgorithmDBDAFNCJ()
Begin
Si=f
//設(shè)置組內(nèi)連通的節(jié)點(diǎn)初始集Si為空
Si←grouphead
If(Gi≠f)
//判斷與組長(zhǎng)連通的相鄰節(jié)點(diǎn)初始集Gi為是否非空
{Si←在Gi集中任選一個(gè)節(jié)點(diǎn)記為k并標(biāo)志為已訪問；
Repeat{if(ki≠f)存在未被訪問的節(jié)點(diǎn)
//判斷與k節(jié)點(diǎn)連通的相鄰節(jié)點(diǎn)初始集ki存在未被訪問的節(jié)點(diǎn)
{Si←在ki集中任選一個(gè)未被訪問過的節(jié)點(diǎn)j,并標(biāo)志為已訪問；
ki=ji;}
ji為與j節(jié)點(diǎn)連通的相鄰節(jié)點(diǎn)集
Else
{回溯到上一個(gè)節(jié)點(diǎn)t
ki=ti;
}
Endif;
}
Until 整個(gè)節(jié)點(diǎn)集合的連通子集都處理完畢
}
Endif
End

DBDAFNCJ算法最后輸出的結(jié)果是在網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)連通的傳感器節(jié)點(diǎn)集，由上述算法可知，DBDAFNCJ算法的時(shí)間復(fù)雜度為О(H)；空間復(fù)雜度為О(N)。其中H為算法探測(cè)的節(jié)點(diǎn)間路徑數(shù)，N為覆蓋區(qū)域內(nèi)的節(jié)點(diǎn)數(shù)。

提出的DBDAFNCJ算法具有的優(yōu)點(diǎn)為：充分利用了基站對(duì)傳感器節(jié)點(diǎn)的所存儲(chǔ)的記憶信息和節(jié)點(diǎn)間相關(guān)路由信息，為部署區(qū)域內(nèi)無線傳感器網(wǎng)絡(luò)后續(xù)研究和使用提供了有效的決策信息；算法的時(shí)間和空間復(fù)雜度比較低，易于實(shí)現(xiàn)。

5仿真實(shí)

通過仿真實(shí)驗(yàn)對(duì)提出的節(jié)點(diǎn)代理方案和DBDAFNCJ算法進(jìn)行性能評(píng)估，下面依次給出實(shí)驗(yàn)方法、環(huán)境和結(jié)果。

5.1實(shí)驗(yàn)環(huán)境

在廣泛使用的網(wǎng)絡(luò)仿真器ns-2的環(huán)境下用C++和TCL實(shí)現(xiàn)了節(jié)點(diǎn)代理方案和DBDAFNCJ算法,實(shí)驗(yàn)設(shè)備是一臺(tái)運(yùn)行RedhatLinux9.0,具有P42.8GHz處理器,512MB DDR內(nèi)存的PC.實(shí)驗(yàn)中，假設(shè)傳感器節(jié)點(diǎn)隨機(jī)部署在1 000m×1 000m監(jiān)測(cè)區(qū)域內(nèi)，基站被隨機(jī)地部署在監(jiān)測(cè)區(qū)域的邊界內(nèi)部，基站的傳輸半徑設(shè)為500m,節(jié)點(diǎn)的傳輸半徑設(shè)為50m，成組節(jié)點(diǎn)分配代價(jià)Acost中的a1和a2的取值各設(shè)定為0.4和0.6，主要考慮到在仿真中由于節(jié)點(diǎn)代理方案中節(jié)點(diǎn)成組代價(jià)比例稍重一些。為模擬第3節(jié)討論的實(shí)際部署區(qū)域中節(jié)點(diǎn)處于基站傳輸范圍之外和存在諸如建筑物等障礙物使得節(jié)點(diǎn)處于孤立狀態(tài)，在各種節(jié)點(diǎn)規(guī)模的仿真中，設(shè)置某一百分比的節(jié)點(diǎn)隨機(jī)部署在基站的傳輸半徑之外，在算法DBDAFNCJ的實(shí)現(xiàn)中，為簡(jiǎn)化起見，且不影響仿真結(jié)果的可靠性，除基站外，其余節(jié)點(diǎn)均只存儲(chǔ)與其只有1跳路由關(guān)系的相鄰節(jié)點(diǎn)，為了快速得到實(shí)驗(yàn)結(jié)果并且不影響仿真結(jié)果的可靠性，把節(jié)點(diǎn)的初始能量設(shè)置為20J，采用模型中節(jié)點(diǎn)能量消耗模型，此時(shí)能量足以滿足實(shí)驗(yàn)條件，選擇一個(gè)簡(jiǎn)化了的定向擴(kuò)散協(xié)議[18]作為網(wǎng)絡(luò)層的路由協(xié)議，修改協(xié)議使節(jié)點(diǎn)間以逐跳的方式進(jìn)行路由。

5.2實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

仿真實(shí)驗(yàn)中，主要考慮部署區(qū)域內(nèi)節(jié)點(diǎn)可達(dá)率NRR（nodereachabilityratio）作為測(cè)試指標(biāo)，計(jì)算如下：

NRR=部署區(qū)域內(nèi)可達(dá)節(jié)點(diǎn)的數(shù)目/部署區(qū)域內(nèi)節(jié)點(diǎn)總數(shù)

在上述仿真實(shí)驗(yàn)環(huán)境下，設(shè)計(jì)了兩類實(shí)驗(yàn)方案對(duì)節(jié)點(diǎn)代理方案和DBDAFNCJ算法進(jìn)行評(píng)估。

1)在部署區(qū)域內(nèi)，改變部署節(jié)點(diǎn)的數(shù)量，固定處于基站傳輸范圍之外的節(jié)點(diǎn)為總節(jié)點(diǎn)20%，把節(jié)點(diǎn)數(shù)目分為100、150、200、250、300、350、400 7種情況進(jìn)行仿真。

2)在部署區(qū)域內(nèi)，固定部署節(jié)點(diǎn)的數(shù)量為300，變化部署處于基站傳輸范圍之外的節(jié)點(diǎn)百分比，把百分比分為5%、10%、15%、20%、25%、30% 6種情況進(jìn)行仿真。

針對(duì)兩類實(shí)驗(yàn)方案，使用DBDAFNCJ算法分別對(duì)使用節(jié)點(diǎn)代理方案部署區(qū)域節(jié)點(diǎn)預(yù)處理前后的節(jié)點(diǎn)連通性進(jìn)行判定，分別記為PRE_DBDAFNCJ和POST_DBDAFNCJ，下面給出實(shí)驗(yàn)結(jié)果。方案1）、2）的實(shí)驗(yàn)結(jié)果分別如圖4、圖5所示。

5.3結(jié)果分析

從圖4和圖5的結(jié)果可以看出，一方面，DBDAFNCJ算法對(duì)于初始部署區(qū)域節(jié)點(diǎn)的連通性比例的判定基本與設(shè)定的節(jié)點(diǎn)連通性比例一致，說明了DBDAFNCJ算法可以很好地對(duì)部署區(qū)域內(nèi)節(jié)點(diǎn)的連通性實(shí)際情況進(jìn)行判定。另一方面，對(duì)于用節(jié)點(diǎn)代理方案處理后的部署區(qū)域使用DBDAFNCJ算法進(jìn)行節(jié)點(diǎn)連通性判定的結(jié)果表明，節(jié)點(diǎn)代理方案較好地改善了部署區(qū)域內(nèi)節(jié)點(diǎn)的連通性情況，方案1）中12%~15%的不可達(dá)節(jié)點(diǎn)實(shí)現(xiàn)了與基站的間接連通；方案2）中3%~12%的不可達(dá)節(jié)點(diǎn)實(shí)現(xiàn)了與基站的間接連通。那些最終還處于不可達(dá)狀態(tài)的節(jié)點(diǎn)是因?yàn)槠?跳范圍內(nèi)沒有基站直接可達(dá)節(jié)點(diǎn)。在現(xiàn)實(shí)情況下，如部署區(qū)域中掉入深坑的節(jié)點(diǎn)、部署完畢即出故障的節(jié)點(diǎn)均可認(rèn)為是此種情況。

6結(jié)束語

對(duì)于隨機(jī)部署在監(jiān)測(cè)區(qū)域的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)連通性的研究是其后續(xù)研究、管理和應(yīng)用的基礎(chǔ)，針對(duì)在實(shí)際應(yīng)用中，節(jié)點(diǎn)隨機(jī)部署而可能出現(xiàn)與基站不能正常通信的問題，提出了一種使用與基站連通的節(jié)點(diǎn)作為代理解決基站不可達(dá)節(jié)點(diǎn)的方案，并基于節(jié)點(diǎn)存儲(chǔ)的路由信息給出了一種節(jié)點(diǎn)連通性的判定算法，仿真實(shí)驗(yàn)中，在改變仿真節(jié)點(diǎn)數(shù)目而固定不可達(dá)節(jié)點(diǎn)比例以及固定仿真節(jié)點(diǎn)數(shù)目而改變不可達(dá)節(jié)點(diǎn)比例2種情況下，結(jié)果均表明所提出的節(jié)點(diǎn)代理方案可以有效地改善部署區(qū)域的節(jié)點(diǎn)不可達(dá)問題，同時(shí)表明，所提出的節(jié)點(diǎn)連通性判定算法能夠高效地探測(cè)部署區(qū)域內(nèi)節(jié)點(diǎn)的連通性狀況。