無線傳感器網絡覆蓋連通性研究

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

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

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

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

5仿真實

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

5.1實驗環(huán)境

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

5.2實驗設計及結果

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

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

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

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

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

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

5.3結果分析

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

6結束語

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