無線傳感器網絡中多Sink節點位置部署研究*

韓凱州， 馬福昌

(1.太原理工大學 新型傳感器與智能控制教育部重點實驗室，山西 太原 030024;2.太原理工大學 測控技術研究所，山西 太原 030024)

0 引 言

無線傳感器網絡(WSNs)，即通過WiFi,Zig Bee等無線方式[1]，使大量的傳感器節點相互聯系、處理、傳輸信息的網絡。在實際應用中，無線傳感器網絡中可能包含一些異構節點，與普通的同構節點相比，這些異構節點除了處理能力更強，計算能力、存儲空間更具優勢以外，也消耗更多的能量。然而在整個網絡中安排適量的異構節點又可以提高整體網絡的數據傳輸能力，從這個角度分析可以延長網絡壽命。因此，異構節點在網絡中對整個網絡的能量消耗和網絡壽命有很大的影響，亦即網絡壽命取決于關鍵節點的壽命。

在許多文獻中都有對異構節點位置部署的研究，這些研究針對不同的模型，提出了例如：Global算法[2]、lhop迭代算法、GEP-MSN算法等[3]。本文將針對非均勻分布的無線傳感器網絡，就異構節點的位置部署問題進行研究分析，利用區域密度優先(RDF)算法進行分析，提出一種方便高效的異構節點位置部署的算法[4,5]。

1 網絡能耗與節點密度的分析

1.1 非均勻分布的節點分布與能耗的關系

在非均勻分布的無線傳感器網絡中，由于傳感器節點隨機的分布，呈不均勻狀態，每個節點所消耗的能量也是不均勻的[6]。Perillo等人根據節點傳輸數據的方式提出2種情況：一種是傳感器節點采用多跳方式向Sink節點傳輸數據，此時離Sink節點較近的節點除需要傳送自己的數據外，還需要轉發其他節點的數據給Sink節點，因此，會消耗更多能量而先于其他節點死亡；另一種是傳感器節點采用單跳方式向Sink節點傳送數據，此時每個節點都只負責發送自己的數據給Sink節點，因此，離Sink節點遠的節點會消耗更多能量而先于其他節點死亡。因此，給定一個非均勻分布的無線傳感器網絡，且該網絡采用的發送方式是多跳，很顯然，在此網絡中部署Sink節點時，應當把Sink節點部署在傳感器節點密度大的地方(圖1)。

圖1 無線傳感器網絡模型

1.2 均勻分布的網絡中節點的能耗

根據文獻知道，傳感器節點最主要的能耗分為感知數據、發送數據和接收數據所消耗的能量三部分，即

(1)

其中,f為單個傳感器節點的數據產生速率;β1,β2分別為發射電路和放大電路的能耗;r為2個節點之間傳輸距離;n為路徑損耗系數(r小于閾值時，n=2；r大于閾值時，n=4)。

在節點均勻分布的無線傳感器網絡中，所有的節點都均勻分布在該網絡里。假定這樣一種情況，網絡分布在半徑為R的圓形區域，Sink節點在圓心，傳感器節點密度為ρ1，傳輸半徑為rc，每個周期傳輸的數據量為f，可得出每個節點能量負載如下:

1)當rc

(2)

2)當rc≥d0,n=4時，能量消耗為

(3)

1.3 非均勻分布的節點的能耗

在節點非均勻分布的無線傳感器網絡中，先考慮一種簡單情況。假設該網絡中Sink節點數為1，在距離該Sink節點lm的范圍內，普通節點的密度為ρ，且每個傳感器節點的能量消耗是均衡的，那么,該網絡應滿足如下公式

(4)

假設在非均勻分布的網絡區域中，區域為x=R的圓形區域，傳感器密度為ρ1，結合式(2)、式(3)，有如下結論：

1)rc

(5)

2)rc≥d0時，得式(6)

(6)

由以上公式可以得出如下結論：當x(傳感器節點到Sink節點的距離)越大時，節點的密度ρ就越小,換句話說，如果每個節點的能耗是相同的，那么,在離Sink節點越遠的地方傳感器節點的分布就越不密集。

2 RDF算法的原理和應用

2.1 RDF算法的提出和原理

大部分關于無線傳感器網絡中異構節點部署的算法[7]，比如遞歸算法等，它們的基本思路都是把Sink節點放置于傳感器節點分布集中的地方，但這些算法大都較為復雜，不利于實現。這里提出的RDF算法，依然沿用上述思路，但相對較為便捷，更利于實現。

如圖2所示，假設傳感器非均勻的分布在一個矩形區域里，將這個區域用直角坐標系將其劃分為4個象限，并用小柵格對每個區域進行劃分，用n1表示柵格的數目。與此同時，每個Sink節點的傳輸范圍用半徑為r的圓盤表示。此外假設每個象限中Sink節點的數量為n2，每個Sink節點傳輸范圍里面的節點數量為n3。

圖2 傳感器網絡象限柵格分割圖

RDF算法具體可以描述為：

1)所有的柵格都是未標記的；

2)對每一個柵格按順序掃描，把Sink節點依次部署于每一個柵格的中心，記錄每一次落入Sink節點覆蓋范圍中傳感器節點的數量；

3)掃描結束后，如果其中一個柵格的節點數量大于其他所有柵格中的節點數量，那么,此柵格為最優柵格；

4)如果有多個柵格的節點數量相同且大于其他所有柵格中的節點數量，那么,考慮2種情況：

a.這些柵格處于同一象限，則其中任一柵格為最優柵格；

b.這些柵格處于不同象限，則部署最少Sink節點的那個象限所對應的柵格就是最優柵格。

2.2 RDF算法分析

從前面的敘述中知道，關鍵節點的壽命決定無線傳感器網絡的壽命，關鍵節點就是落在Sink節點通信范圍內的傳感器節點[8]。當網絡里存在多個Sink節點時，要求這些關鍵節點可以平均地承擔普通節點的數據傳送功能。由2.1節的結論可以知道，RDF算法通過選取最優柵格，較好地解決了這個問題。

由文獻知道，一個確定異構節點位置的無線傳感器網絡的壽命可以表示為

(7)

給上式中的參數選取一定的數值，圖3顯示的就是當網絡中部署了1～5個Sink節點時網絡壽命的時間。

圖3 網絡壽命

3 算法仿真

為了綜合分析和驗證本文本文中描述的RDF算法，對RDF算法、遞歸算法以及隨機分布3種情況的網絡壽命和報文的遞交概率在Matlab上進行了多次仿真，證明了RDF算法在這兩方面都更具優勢。

3.1 場景設計

假設100個傳感器節點隨機分布在1 000 m×1 000 m的矩形區域里面，Ei=100 J，εt=0.015 J，εr=0.015 J，εt=0.5 J。Sink節點數量為1～9。

3.2 仿真結果

3.2.1 不同部署算法網絡壽命的比較

如圖4所示，RDF算法和遞歸算法下部署的Sink節點的網絡，其壽命基本接近，隨機分布的壽命則小于二者，說明RDF算法在延長網絡壽命方面作用明顯，且比遞歸算法更簡單方便利于實現。

圖4 不同部署策略下網絡壽命

3.2.2 不同部署算法報文的遞交概率的比較

報文遞交概率是對網絡壽命檢測的一項主要指標，如圖5所示，RDF算法和遞歸算法的保溫遞交概率更高于隨機分布的情況，而RDF算法相對更簡單便捷利于實現。

圖5 不同部署策略下報文遞交概率的比較

4 結束語

本文在分析了隨機分布的無線傳感器網絡能耗和節點密度的關系，在此基礎上提出了RDF算法，該算法以優化傳感器網絡中的Sink節點的部署來達到降低能耗的目標。通過仿真實驗證明：RDF算法在重新恢復連通度時比遞歸算法的連通度高且異構節點放置位置優越。雖然在網絡壽命上RDF算法和遞歸算法相接近,但是,RDF算法更適合實際應用。因此，RDF算法是一種簡便可行的算法。

參考文獻:

[1] 王永杰，楊小平.基于無線傳感器網絡的智能小區監控系統設計[J].制造業自動化,2011,33(1):68-70.

[2] Dai S,Tang C,Qiao S,et al.Optimal multiple sink nodes deployment in wireless sensor networks based on gene expression programming[C]∥The Second International Conference on Communication Software and Networks,ICCSN’10:IEEE,2010:355-359.

[3] Vincze Z,Vida R,Vidacs A.Deploying multiple sinks in multi-hop wireless sensor networks[C]∥IEEE International Conference on Pervasive Services,IEEE,2007:55-63.

[4] Gu Y,Wu Q,Cai X,et al.On efficient deployment of high-end sensors in large-scale heterogeneous WSNs[C]∥ IEEE 6th International Conference on Mobile Ad Hoc and Sensor Systems,MASS’09,IEEE,2009:912-917.

[5] Friedmann L,Boukhatem L.Efficient multi-sink relocation in wireless sensor networks[C]∥Third IEEE International Confe-rence on Networking and Services(ICNS),2007:90.

[6] 張萃玲,陳志剛,劉安豐,等.非均勻部署 WSN 的能量空洞避免策略[J].計算機工程,2010,36(2):83-86.

[7] Wang Q,Xu K,Takahara G,et al.Device placement for heterogeneous wireless sensor networks:Minimum cost with lifetime constraints[J].IEEE Transactions on Wireless Communications,2007,6(7):2444-2453.

[8] Xu K,Wang Q,Hassanein H,et al.Optimal wireless sensor networks (WSNs) deployment:Minimum cost with lifetime constraint[C]∥IEEE International Conference on Wireless and Mobile Computing,Networking and Communications,(WiMob’2005),2005:454-461.