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

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

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

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

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

5仿真實

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

5.1實驗環境

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

5.2實驗設計及結果

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

NRR=部署區域內可達節點的數目/部署區域內節點總數

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

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

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

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

5.3結果分析

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

6結束語

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