一種基于元胞自動機的無線傳感器網絡拓撲控制方法*

史 倢，陳 志，2，3，* ，章 韻，扈羅全，岳文靜

(1.南京郵電大學計算機學院，南京 210003； 2.南京大學計算機軟件新技術國家重點實驗室，南京 210093； 3.江蘇省無線傳感網高技術研究重點實驗室，南京 210003； 4.寬帶無線通信與傳感網技術教育部重點實驗室，南京 210003； 5.蘇州出入境檢驗檢疫局，江蘇蘇州 215104)

無線傳感器網絡是一種由大量傳感器節點組成，通過無線方式協作地檢測、感知和處理各種環境或者檢測對象信息的網絡系統［1－3］，傳感器網絡節點通常由電池供電，通信、計算、處理能力有限，對該網絡進行拓撲控制的目標是尋找一種節點的配置方法，在減少系統能量消耗的前提下，保證整個網絡拓撲的連通性和覆蓋性。

元胞自動機(Cellular automata)作為狀態離散系統，能夠以簡單的規則揭示復雜的全局特性，因而成為研究自組織時空演化規律的重要工具［4］。文獻［5］將元胞自動機作為一種模擬無線傳感器網絡行為的工具，認為無線傳感器網絡節點之間具有的高度協作性，形成類似于元胞自動機所模擬的大部分動力學系統。文獻［6］在無線傳感器網絡的元胞自動機模型基礎上，提出一種節點可動態調節通信范圍的方法。文獻［7］通過建立無線傳感器網絡的二維元胞自動機模型，分析節點狀態規則和網絡拓撲覆蓋性與連通性的關系，并將無線傳感器網絡的整體拓撲特性初步歸納為震蕩、衰減、穩定等基本模式。

上述研究將無線傳感器網絡平面看成是按照正方形網絡排列的二維元胞空間，每個格點對應一個傳感器節點，具有工作和休眠兩種狀態。鄰居定義為與元胞相鄰的8個元胞，即Moore型鄰居［8］。每個元胞根據鄰居狀態的變化改變自身狀態。通常情況下，傳感器節點由隨機散布方式部署，并非規則分布，并且節點自身能量有限，隨著網絡的運行，可能因為能量耗盡而失效。因此，本文在此基礎上擴展元胞狀態為3種，即元胞處無節點對應/節點失效、節點休眠、節點工作，元胞以隨機方式部署，尋找元胞最優狀態演化規則，以實現在保證網絡覆蓋率和連通度的前提下減少能耗。

1 基于元胞自動機的拓撲控制模型

1.1 元胞自動機模型

以Conway的生命游戲［9］為例，生命游戲描述的是生物群體的生存繁殖規律:在生命密度過小時，由于孤單使生物體缺乏配種繁殖機會、缺乏互助導致生命危機，生物體由生變為死；在生命密度過大，由于資源缺乏、相互競爭也會出現生存危機，生物體也由生變為死；只有處于個體適中狀態的生物才能生存并繁衍后代［4］。

用元胞自動機模型表示為:

(1)元胞分布于規則劃分的二維網格上；

(2)元胞具有兩種狀態:0死，1生；

(3)元胞的狀態由上一時刻自身的狀態和鄰居狀態決定，鄰居為與元胞相鄰的8個元胞；

(4)演化規則用數學表示為S23/B3，即:

1.2 無線傳感器網絡的元胞自動機模型

無線傳感器網絡運行狀態類似于生命游戲，如果利用網絡中的所有節點進行監測會產生冗余，也就是說，在同一時刻會有2個或2個以上的節點監測同一個區域，不僅浪費能源，而且在傳輸數據包的過程中會產生碰撞和阻塞；如果節點周圍鄰居過少，那么節點也會因為負載過大、能量耗盡而失效。因此節點的工作/休眠機制成為節省能耗、延長網絡壽命的一種有效手段。工作/休眠機制即在合適的時間［10－13］關閉節點發射器，讓其進入睡眠狀態，以大幅減小能量消耗。

本文考慮無線傳感器網絡節點經部署初始化后有三種狀態:工作、休眠、失效(或空位)。傳感器節點具有固定的工作/休眠周期，即當工作(休眠)一定時間T后進入休眠(工作)狀態。每個傳感器節點具有一定的初始能量E0，當處于工作狀態時，打開發射器進行接收、轉發、監聽等操作，因此需要消耗大量的能量Ew，當其處于休眠狀態時，關閉發射器進入低功率狀態，消耗較少的能量Es，隨著網絡的運行，節點工作、休眠狀態交替改變，能量耗盡，節點失效，則節點狀態變為失效。由于該方法隨機性較大，可能隨著部分節點的失效導致網絡的覆蓋率、連通度下降，影響網絡的整體性能。因此，需要節點之間具有高度的協作性，節點在固定的時間段檢測鄰居狀態，在保證自己監測的區域內已有足夠的節點監測后再進入休眠，同樣，處于休眠狀態的節點發現該區域內工作節點不足時，及時醒過來進入工作狀態。

基于二維元胞自動機的無線傳感器網絡模型敘述如下:

(1)元胞狀態集S={0，1，2}，0 表示無節點/節點失效，1表示節點處于休眠狀態；2表示節點處于工作狀態。

(2)元胞鄰居集合N定義為節點功率半徑R范圍內所有節點(包括邊界)。

(3)每個元胞的狀態由上一時刻鄰居元胞狀態以及自身狀態決定。具體演化規則如下:

如果元胞在t時刻為2，且其鄰居狀態為2的個數為Ni，那么t+Δt時刻元胞狀態不變；

如果元胞在t時刻為1，且其鄰居狀態為2的個數為Nj，那么t+Δt時刻元胞狀態改變為2。

上述規則中:Δt表示一個時間間隔；Ni和Nj是選擇最優演化規則的兩個常量，表示最佳鄰居節點個數。

2 基于元胞自動機的拓撲控制方法

2.1 方法流程

根據無線傳感器網絡的元胞自動機模型，可以建立基于元胞自動機的拓撲控制方法，首先做兩點假設:

(1)假設傳感器網絡為同質網絡，即所有節點的大小、形狀、結構以及具有的初始能量相同。

(2)假設通信模塊的發送半徑和接收半徑相同。

在上述假設條件下，基于元胞自動機的拓撲控制流程如下:

(1)在規模為L元胞空間內隨機部署N個狀態非0的元胞，令其中70%的元胞狀態為1(休眠)。所有元胞具有固定的工作/休眠周期選擇工作或休眠，令該周期為T=kΔt。

(2)在每個時間間隔Δt中，元胞根據上述模型中的演化規則改變自身狀態，即由上一時刻鄰居元胞狀態和元胞自身狀態決定。

(3)每個元胞具有一定的初始能量E0，每個時間間隔Δt中，元胞狀態為工作時消耗能量Ew，元胞處于休眠狀態(也稱低功耗狀態)時消耗較少的能量Es，當元胞能量全部消耗后，元胞失效。

上述流程中，規模L、節點個數N、時間間隔Δt、工作/休眠周期T、元胞初始能量E0、工作狀態消耗能量Ew、休眠狀態消耗能量Es等參數可根據實際應用情況進行選擇。

2.2 評價參數

為評價基于元胞自動機的無線傳感器網絡拓撲控制方法性能，定義如下二維元胞模型的拓撲特性:

(1)覆蓋率

不考慮邊界節點覆蓋面積的減少，每個傳感器節點的通信半徑為R，那么一個節點的覆蓋概率為p=πR2/L2。

令一個節點的覆蓋概率為p(A)=p，那么兩個節點的覆蓋概率為

依次，n個節點的覆蓋概率為

(2)連通度

無線傳感器網絡作為信息收集系統，需要實現多跳的信息傳輸，在元胞自動機模型中表現為活著的元胞擁有活著的鄰居［6］。處于工作狀態元胞的鄰居中無處于工作狀態的元胞，則對網絡連通率的貢獻為0。所以，連通度表示為區域內(所有工作節點個數－鄰居節點未處于工作狀態的工作節點個數)/所有工作節點個數。

(3)能耗指數

某一時刻工作節點占所有節點的比重表示網絡該時刻的能耗指數。能耗指數越高，說明該時刻工作節點個數越多，能量消耗越大。

3 仿真分析

我們利用MATLAB進行仿真研究，定義元胞自動機的規模為L，初始元胞總數為L2，試驗中取L=50。根據實際網絡特點，采用周期性邊界條件。網絡初始化為隨機部署750個元胞，即令30%的元胞狀態為1，并在所有狀態為1的元胞中以30%概率取2。元胞半徑R=3。取Δt為1個時間步，連續工作/休眠周期為3個時間步，元胞初始能量為0.8 J，每個時刻中，工作狀態消耗能量0.016 5 J，休眠狀態消耗能量0.000 08 J。仿真研究兩個方面內容:①研究在不同的局部更新規則下，系統的覆蓋率、連通度和能耗指數的時間演化特征；②研究基于元胞自動機的無線傳感器網絡拓撲控制方法與節點隨機部署后采用隨機休眠/工作機制下的拓撲特性。

3.1 最佳局部更新規則

在不同的規則下，系統呈現出復雜的時空演化特性。圖1所示為采用S34/B23規則下的網絡覆蓋率和連通度的變化情況。從圖1可見，系統的覆蓋率和連通度經過有限次震蕩以后逐步趨于穩定，說明在此網絡狀態下，當每個傳感器節點處于工作狀態的鄰居數為3或4時，網絡能夠通過一定時間的自適應調節后保持一個相對穩定的拓撲狀態。當處于工作狀態的鄰居數大于4或小于3個時，測試顯示覆蓋率和連通度始終處于震蕩狀態，說明網絡中工作節點的密度不均衡，造成網絡覆蓋率和連通度周期震蕩，影響網絡的整體性能。另外，從圖中可以看出，當休眠概率保持在70%左右時(即保持網絡中30%的節點處于工作狀態)，即可保證網絡具有良好的覆蓋率和連通度。

圖1 規則S34/B23下網絡覆蓋率和連通度的變化情況

3.2 基于元胞自動機的拓撲控制方法

如圖2所示，當系統運行至100步時，采用隨機休眠/工作機制的網絡中節點能量完全耗盡，而基于元胞自動機方法的網絡中運行到110步時才逐漸有節點失效，剩余節點數開始逐漸減少，基于元胞自動機方法的網絡壽命比隨機休眠/工作機制的網絡壽命延長80%左右。

圖2 兩種方法隨時間變化剩余節點數和能耗指數的變化情況

圖3 兩種方法隨時間變化休眠概率、覆蓋率、連通度的變化情況

圖3給出節點休眠概率、覆蓋率和連通度的變化情況。圖3(a)中隨機工作/休眠機制節點休眠，圖3(b)、3(c)所示采用元胞自動機方法的網絡覆蓋率和連通度有小幅度的震蕩，但基本都在90%左右，說明網絡能夠較好地自適應調整其拓撲狀態。相對于定時工作/休眠的情況而言，基于元胞自動機的拓撲控制方法在沒有影響網絡覆蓋率和連通度的前提下，減少了網絡系統能耗，延長了網絡運行壽命。

4 結束語

拓撲控制是研究實現無線傳感器網絡能量高效利用的主要技術之一，工作/休眠機制是拓撲控制研究中一個重要的部分。利用元胞自動機對無線傳感器網絡進行建模，有利于研究與控制節點間相互作用導致的網絡拓撲動態變化。本文在隨機休眠/工作機制的基礎上，提出了一種適用于一般性無線傳感器網絡的元胞自動機模型，建立了基于該模型的拓撲控制方法，仿真表明該方法在保證網絡覆蓋率的前提下減少了能量消耗，延長了網絡壽命。

在今后的工作中，我們將結合更多問題，考慮與其他拓撲控制算法進行比較，進一步深化元胞自動機在無線傳感器網絡中的應用。另外，元胞自動機在無線傳感器網絡中的應用多針對同質網絡，今后的研究可以擴展多層次的元胞自動機模型以實現異質網絡拓撲控制。

［1］王殊，閻毓杰，胡富平，等.無線傳感器網絡的理論及應用［M］.北京:北京航空航天大學出版社，2007.7.

［2］陳志，史倢，章韻，等.基于Agent的無線傳感器網絡AUML交互模型［J］.傳感技術學報，2010，23(11):1617－1622.

［3］章韻，王靜玉，陳志，等.基于Q學習的無線傳感器網絡自組織方法研究［J］.傳感技術學報，2010，23(11):1623－1626.

［4］賈斌，高自友，李克平，等.基于元胞自動機的交通系統建模與模擬［M］.北京:科學出版社，2007.

［5］Cunha R O，Silva A P，Loreiro A F F，et al.Simulating Large Wireless Sensor Networks Using Cellular Automata［C］//IEEE Proceedings of the 38th Annual Simulation Symposium，April 2005:323－330.

［6］Sepideh Adabi，Ahmad Khadem Zadeh，Arash Dana，et al.Cellular Automata Based Method for Energy Conservation Solution in Wireless Sensor Network［J］.Wireless Communications，Networking and Mobile Computing，2008:1－5.

［7］張文鑄，袁堅，俞哲，等.基于元胞自動機的無線傳感器網絡整體行為研究［J］.物理學報，2008，57(11):6896－6900.

［8］Jarkko Kari.Theory of Cellular Automata:A Survey［J］.Theoretical Computer Science，2005.334(1－3):3－33.

［9］Gardner M.The Fantastic Combination of John Conway’s New Solitaire Game Life［J］.Scientific American，1970，220(4):120－123.

［10］Ye F，Zhong G，Lu S，et al.PEAS:A Robust Energy Conserving Protocol for Long-Lived Sensor Networks［C］//Proceeding of the 23rd International Conference on Distributed Computing Systems，2003:28－37.

［11］Yan T，He T，Stankovic J A.Differentiated Surveillance for Sensor Networks［C］//Proceeding of the First ACM Conference on Embedded Networked Sensor Systems(Sensys03)，2003:51－62.

［12］Wang X，Xing G，Zhang Y，et al.Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks［C］//Proceeding of ACM SIGMOBILE International Conference on Embedded Networked Sensor Systems(SenSys 2003)，Los Angeles，CA，USA，2003:28－39.

［13］石高濤，廖明宏.大規模傳感器網絡隨機睡眠調度節能機制［J］.計算機研究與發展，2006，43(4):579－585.

［14］孫永進，孫雨耕，房朝暉.無線傳感器網絡的連通與覆蓋［J］.天津大學學報，2005，38(1):14－17.