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

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

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

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

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

5仿真實

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

5.1實驗環(huán)境

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

5.2實驗設(shè)計及結(jié)果

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

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

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

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

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

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

5.3結(jié)果分析

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

6結(jié)束語

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