基于元胞自動機的無線傳感網路由節能技術

于 秦，王偉東，冷甦鵬，毛玉明

(電子科技大學光纖傳感與通信教育部重點實驗室 成都 611731)

基于元胞自動機的無線傳感網路由節能技術

于 秦，王偉東，冷甦鵬，毛玉明

(電子科技大學光纖傳感與通信教育部重點實驗室 成都 611731)

針對無線傳感器網絡(WSN)路由協議設計需首要解決的節能問題，提出一種將元胞自動機(CA)用于無線傳感器網絡的高效節能機制。該機制在路由層設置元胞處理模塊，通過路由報文捎帶CA信息網絡節點自組織形成以sink節點為中心的多級元胞自動機區域，決策節點根據通信過程中攜帶的元胞信息切換傳感節點的工作狀態以實現節能。仿真結果驗證了該機制能降低網絡整體能量消耗，提高能量利用率，延長整個網絡生存周期。

元胞自動機; 節能; 路由; 無線傳感器網絡

無線傳感器網絡(WSN)是一種涉及多學科的新型無線網絡。它綜合了傳感器技術、網絡通信技術、無線傳輸技術、嵌入式計算技術、軟件編程等技術，是通信和計算機科學的一個研究熱點領域。WSN網絡通常部署在自然環境復雜的區域，節點的供電非常有限。因此如何在保證數據傳輸可靠性沒有明顯降低的情況下，盡量減少節點能耗是目前研究的主要方向之一。

目前WSN節能的研究雖取得了一些成果，但仍存在以下問題：未能使用網絡仿真軟件對二維元胞自動機進行網絡仿真；尚處于數學算法研究階段；缺少將元胞自動機技術與網絡協議相融合的實例。文獻[1]提出一種基于IEEE 802.15.4/Zigbee網絡的整體休眠策略，核心思想是以劃分時隙的方式實現整個網絡同步工作或休眠，即包括路由節點在內的所有節點在工作時間傳輸并儲存數據信息。當休眠時隙到來時所有節點休眠，工作時隙到來時所有節點工作，傳輸緩存的數據信息。文獻[2]針對將元胞自動機模型用于無線網絡拓撲控制的問題，提出基于覆蓋度和連通度的考量標準下的元胞自動機模型，建立該模型的拓撲控制方法，并仿真其有效性。文獻[3]基于IEEE 802.15.4/Zigbee網絡比較AODV協議與樹形路由Zigbee協議在節能上的表現，提出了一種混合路由機制。文獻[4]提出基于元胞自動機的動態自組織算法，節點根據鄰居節點的工作/休眠狀態切換自身工作狀態，平均節點能耗。但該機制缺少全局控制的針對性，對待檢測區域缺乏可靠性，不適用于無線多跳網絡。文獻[5-6]指出自組織網絡性質的決定性因素在于系統節點之間的內在交互作用，而不是外界干擾或邊界條件的影響。

本文基于元胞自動機機制，在路由層設置元胞處理模塊(CA-modular)，通過路由報文中捎帶CA信息，網絡節點自組織形成以sink節點為中心的多級元胞自動機區域。sink節點元胞處理模塊根據CA信息和狀態轉換機制決策是否應使某些子節點進入休眠狀態。休眠節點定時器超時時，節點恢復工作狀態。該機制能降低無線傳感網絡整體能量消耗，提高能量利用率，延長整個網絡生存時間。

1 無線傳感網絡的元胞自動機模擬

二維元胞自動機(CA)是一類時間、空間、狀態都離散的動力學系統，其基本特點是：散布于規則網格中的每一元胞均取有限的離散狀態，各元胞遵循相同的演化規則進行更新[7]。元胞自動機的核心元素包括：節點狀態集合、節點狀態總數、節點鄰居集合和節點狀態轉換規則。即元胞自動機A可以用4元組表示為A=(S,k,N,f )，其中，S代表節點所有可以處于的狀態，k代表節點的狀態總數，N為節點鄰居集合，F為狀態轉換規則[8]。

無線傳感網絡由大量分布式的微小傳感器節點構成，每個節點只能與周圍臨近的節點進行通信，并依靠局部信息做出行為決策。而元胞自動機能夠以簡單的規則揭示復雜的全局特性，并且結構簡單、易于計算機實現。因此，本文首先構建面向無線傳感網絡的二維元胞自動機模型。該模型建立二維元胞自動機與實際無線傳感網絡的映射關系，包括元胞空間與節點空間、元胞鄰居集與節點鄰居集、元胞狀態集與節點狀態集、元胞狀態轉換規則與節點狀態更新等要素間的對應關系。

考慮一個平面分布的無線傳感器網絡，N個靜態獨立的傳感節點以隨機的方式布撒在一個包含L×L個格子單元的規則二維網格中，網格即代表一個二維元胞空間。為簡化分析，假設一個網格單元至多包含一個傳感節點，這個平面無線傳感網即構成元胞空間，一個傳感節點就是元胞空間中的一個元胞。任何節點在空間中的位置可以用該二維網格中的水平坐標i和垂直坐標j唯一標識。記C(i,j)表示處于(i,j)坐標的節點或元胞。元胞空間記為：

由于信號強度路徑衰減，每個節點存在最大通信距離Rc，二維元胞模型中的鄰居定義由該最大通信距離決定。定義節點鄰域為Moore型結構，定義節點C(i,j)的通信鄰居集合為：

本文考慮傳感器節點采用S-MAC協議，即每個節點在每個round周期按照工作與休眠兩個階段的方式工作。節點根據喚醒規則選擇自己處于工作狀態或休眠狀態。當處于工作狀態時，節點則對周圍環境進行檢測并進行必要的處理；而處于休眠狀態時，節點將進入休眠狀態以節省能量。因而可以定義k=2，S={1,0}?！?”狀態表示節點工作；“0”狀態表示節點休眠。

對于任意節點C(i, j)，按照狀態轉移規則有:

即1t+時刻的節點狀態是由t時刻該節點鄰居狀態按照一定規則f(?)確定的。

2 基于多級分區元胞自動機的多跳無線傳感網絡路由節能技術

無線傳感器網絡中隨機散布的sensor傳感器節點以自組織形式構成網絡，通過多跳中繼方式將監測數據傳到sink節點。本文的無線傳感網絡拓撲形式為星形，由一個中心sink節點和若干sensor傳感器節點組成。sensor傳感器節點為同質性節點，具有數據采集和數據中繼功能，所有sensor傳感器節點將數據傳輸至中心sink節點。中心sink節點能量無限且一直處于工作狀態。只有中心sink節點有決策休眠功能，即sensor節點的休眠或工作狀態由中心sink節點控制。

圖1 基于多級分區元胞自動機的多跳WSN

sensor節點啟動后，以sink節點為邏輯中心自組織形成多個元胞自動機CA區域，如圖1所示。CA區域共包括3種等級節點。中心sink節點為零級節點，sink節點單跳通信范圍內的sensor傳感器節點為第一級節點，第一級節點單跳通信范圍內的sensor傳感器節點為第二級節點。sensor節點的通信級別至多兩級。節點啟動時不具有等級信息，通過CA區域構建過程確定節點等級，且僅具有唯一一種等級。數據傳輸過程中，第二級節點傳輸數據經第一級節點至sink節點。

在CA區域的構建完成后，每間隔一段時間，sink節點根據鄰居節點(第一級節點)的能量狀態信息，選擇部分能量較低的節點進入休眠狀態，鄰居節點收到休眠通告后轉發給下屬的第二級節點并進入休眠狀態。節點休眠前設置休眠定時器，當休眠定時器超時時，恢復工作狀態。

圖2 協議棧

該系統需要修改節點協議棧，在路由層添加CA處理模塊。CA模塊采用事件驅動機制，記錄并更新鄰居狀態集N，實現元胞自動機的狀態轉換規則f(?)。協議棧如圖2所示。在通信過程中，節點路由層報文將附加CA處理模塊的CA信息，以捎帶的形式隨路由報文傳輸。CA信息包括信息類型、節點ID號和節點剩余能量，其中信息類型如下面所述的CA_start、CA_startsecond和CA_response等。收到路由報文的節點根據報文中的CA信息更新本地的CA信息表并根據狀態轉換規則切換工作與休眠狀態。

2.1 CA區域構建

CA區域構建過程中的報文交互如圖3所示，構建步驟如下所述。

圖3 CA區域構建的報文交互過程

1) sink節點和sensor節點開機。sink節點查詢本地CA表，CA表記錄了鄰居節點的節點ID、節點等級和剩余能量信息。若CA表為空則觸發CA區域構建過程。

2) sink節點將CA構建信息(報文頭部的信息類型字段為Type_CA_start類型)置于目的地址為廣播的路由報文中發送(如AODV路由協議中的request類型和hello類型報文)，發起CA區域構建。定義該類報文為CA_start。

3) 收到CA_start報文的節點，將自身節點的類型定義為第一級節點。首先構建CA_response類型報文(報文頭部的信息類型字段為Type_CA_response)，隨目的地址為源節點的單播路由報文(如AODV路由協議中的response類型報文)發送給源節點，此處源節點即步驟2)中所述的sink節點；然后構建CA_startsecond類型報文(報文頭部的信息類型字段為Type_CA_startsecond)，用于第一級節點發現并建立與第二級節點的聯系。報文構建完成后置于目的地址為廣播的路由報文中發送。

4) sink節點收到CA_response報文后，記錄該節點IP、級別和能量等信息于自身CA表中。

5) 無級別的sensor節點收到CA_startsecond類型報文時，將自身節點的類型定義為第二級節點，構建報文CA_response，發送給源節點。一個已經有級別的sensor節點再收到CA_start或CA_startsecond類型報文時，若自身級別小于構建報文級別時(CA_start為第一級報文，CA_startsecond為第二級報文)，將放棄原級別，改為新級別，即某區域的第二級節點可以變為其他區域的第一級節點。

6) 若某節點處于sink節點兩跳通信范圍以外則有可能無法成為任何節點的子節點，這種類型的節點被稱為無等級節點。無等級節點不能進入休眠狀態。因此在網絡部署時應盡量保證各CA區域范圍之和能覆蓋全部節點。至此，CA區域構建完成。

2.2 轉換規則設計

無線傳感器網絡對于待檢測區域采取冗余配置的方式，使用多個傳感節點對同一區域或目標進行檢測，保證數據采集可靠性。對同一區域或目標的檢測通常是重復性的，因此在保證可靠傳輸的基礎上，使部分冗余節點進入休眠狀態以節省能量是必要且有效的。

本文定義的轉換規則如下：除sink節點外的其他節點取0/1兩種狀態，分別代表休眠和工作狀態。sink節點根據當前狀態和狀態轉換規則決策部分子節點進入休眠狀態。子節點進入休眠狀態前，通告其自身的所有子節點進入休眠狀態。節點進入休眠時設置休眠定時器，定時器超時時節點恢復工作狀態。

影響sink節點決策休眠的因素主要體現在無線傳感器網絡節點冗余配置情況和節點的剩余能量兩個方面，可表示為：

式中，N_sleep表示可以休眠的節點數：R表示冗余率；N表示網絡總節點數；k為冗余節點中進入休眠狀態的節點比例。

無線傳感器網絡節點冗余配置情況將影響休眠決策，由式(5)可見，sink節點根據網絡冗余率R計算鄰居節點中冗余節點個數，判定冗余節點個數的k%進入休眠狀態。此外，節點剩余能量將影響休眠決策。每個第二級sensor節點定時向第一級sensor節點匯報能量情況，第一級sensor將自身能量和所有第二級sensor 節點能量計算平均值后，發送給sink節點。sink節點記錄第一級sensor節點通告的剩余能量情況。

2.3 休眠與喚醒過程

sink節點記錄第一級sensor節點通告的剩余能量情況，根據冗余率R和式(5)計算可以進入休眠狀態的節點個數。sink選擇剩余能量最少的N_sleep個第一級sensor節點，對這些節點發送休眠通告報文。休眠通告報文隨目的IP地址為廣播的路由報文發送，具有類型字段值為Type_sleep和節點ID字段。收到廣播路由報文的節點根據類型字段值和節點ID字段值，識別自身節點是否為可休眠節點。若自身節點為可休眠節點，則對本節點的子節點發送休眠通告報文?？尚菝吖濣c設置休眠定時器后進入休眠狀態，休眠定時器持續時間t秒后喚醒節點。休眠狀態節點不具有發送接收功能。當休眠定時器超時時，節點恢復工作狀態。

子節點收到休眠通告報文后同樣完成上述過程。第二級節點不能發送休眠通告報文。無等級節點不能進入休眠狀態，因此在網絡部署時應盡量保證各CA區域范圍之和能覆蓋全部節點。

本文定義休眠/喚醒周期時長為2倍休眠定時器持續時間，用以避免節點頻繁地在工作和休眠狀態之間切換，從而保證網絡的穩定性。sink節點在每個休眠/喚醒周期對子節點進行一次狀態轉換決策。

3 仿真及結果分析

利用NS2仿真軟件對基于元胞自動機模型的無線網絡進行模擬。仿真中考慮了兩種類型的無線傳感網絡：1) 網絡的節點為未加入元胞自動機處理過程的普通節點；2) 網絡的節點為加入了元胞自動機的CA節點。對這兩類無線傳感網絡的總體能量消耗、能量利用率和傳輸率進行了比較，并且限制節點能量，仿真兩種模式下剩余節點數隨時間變化的情況。

仿真拓撲分別設置為55×格狀拓撲和77×格狀拓撲，如圖4所示。在55×格狀拓撲中，拓撲中心有1個sink節點接收傳感數據和決策休眠；77×格狀拓撲，在拓撲中有3個sink節點接收傳感數據、劃分CA區域和決策休眠。拓撲方格中I代表在CA區域劃分后成為第一級節點，II代表將成為第二級節點，none代表將成為無等級節點。每一個CA區域以sink節點為中心，其邊緣節點可能是第二級節點也可能是第一級節點。每一個節點只存在于一個CA區域中，不會存在區域重疊節點。表1為仿真參數設置。

表1 仿真參數設置

圖4 仿真拓撲

圖5為55×拓撲和77×拓撲的整體能量消耗。在此過程中節點能量無限。能量消耗包括傳感節點發送、接收和偵聽過程中的能量消耗。節點從第50 s開始發送傳感數據。采用CA機制后，節點首先完成CA區域構建，然后sink可以根據節點工作狀態決策部分節點進入休眠狀態，因此，降低了整體能量消耗。對55×拓撲和77×拓撲，總能量消耗大致分別減少了10%～30%。

圖5 整體能量消耗圖

圖6比較了兩種網絡的能量利用率。t時刻的能量利用率為t時刻以前傳輸數據報文所消耗的總能量與t時刻以前傳輸所有報文所消耗的總能量之比。由圖6可見，采用CA機制后能量利用率提高了10%～20%。并且節點數少時，能量利用率高于節點數多時的能量利用率。分析其原因在于，當節點數增多時，在路由等方面的開銷更多，CA區域構建過程更復雜，時間更長，導致能量利用率下降。通過使用CA處理機制，使節點在合適的情況下休眠，可以降低網絡沖突，減少空閑偵聽和沖突重傳帶來的開銷，從而提高能量利用率。

圖6 能量利用率

在圖7中，限制每個節點的能量上限為4 J，在正常工作模式下約可以工作500 s。由于不同節點的負載不同，負載重的節點能量消耗快，負載輕的節點能量消耗相對慢一些，所以不是所有節點在同一時刻能量耗盡，而是整個網絡中的節點能量逐漸耗盡。由圖7可見，采用CA機制后節點生存時間明顯變長，節點能量耗盡速度明顯下降，整個網絡的生存期得到提高。

圖8展示了兩種拓撲下采用CA機制和未采用CA機制的傳輸率對比。t時刻的傳輸率為t時刻以前PAN節點收到的數據報文個數與t時刻以前傳感節點發送的數據報文個數之比。傳輸率能夠從整體上準確反映網絡傳輸可靠性。由圖8可見，網絡運行初期，采用CA機制與未采用CA機制的傳輸率均在80%以上，能夠保證傳輸可靠性，滿足用戶的可靠性需求。隨著節點能量的消耗，未采用CA機制的網絡的傳輸率明顯下降，逐漸下降至80%以下。節點采用CA機制后，sink節點協調部分節點進入休眠狀態，保證了網絡的整體穩定性。開啟CA機制后，曲線出現交疊現象的一個原因是節點在休眠和工作狀態進行切換，影響了數據傳輸路徑和可靠性。某時刻進入休眠狀態的節點多，網絡傳輸率下降; 某時刻進入休眠狀態的節點少，網絡傳輸率上升，從而使曲線在一定范圍內浮動。而對于未開啟CA機制的網絡，隨著路由的建立，整體網絡趨于穩定，從而傳輸率基本穩定。

圖7 節點生存時間

圖8 傳輸率

4 結 論

本文提出了一種基于多級分區元胞自動機的多跳無線傳感器網絡路由節能技術。通過設計元胞自動機狀態轉換規則，中心sink節點選擇部分剩余能量低的sensor節點進入休眠狀態，從而使得節點能夠通過元胞自動機的狀態轉換規則，在休眠和工作狀態間進行切換。剩余能量等信息隨路由報文傳輸，無需增加額外的開銷。本文的休眠決策機制通過合理使用元胞自動機處理機制，在網絡層的路由協議中添加CA處理模塊，在保證網絡傳輸可靠性的基礎上，減少了節點能量消耗。仿真驗證了使用CA處理機制在網絡傳輸率沒有大幅下降的前提下，在減少能量消耗、延長網絡生存期和提高能量利用率上的良好效果。在后續研究中，將進一步對基于元胞自動機的無線傳感網絡節能問題展開更深入研究。針對具有自組織特性的無線傳感網絡時空演化規律，研究如何在盡量減少系統能量消耗的前提下，保證無線傳感網絡拓撲的連通性和覆蓋性。

[1] SHI J, CHEN Z, ZHANG Y, et al. Cellular automata based topology control method for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2011, 24(12): 1734-1738.

[2] VISWANATHAN A, BOULT T E. Power conservation in Zigbee networks using temporal control[C]//Proceedings of IEEE International Symposium on Wireless Pervasive Computing. Puerto Rico, India: IEEE, 2007: 327-331.

[3] RAN P, SUN M H, ZOU Y M. ZigBee routing selection strategy based on data services and energy-balanced Zigbee routing[C]//Proceedings of IEEE Asia-Pacific Conference on Services Computing. Guangzhou: IEEE, 2006: 400-404.

[4] FAN T H, XIAO X J, YIN L L, et al. Cellular automata self-organization algorithm for wireless sensor network[J]. Computer Engineering, 2009, 35(21): 26-28.

[5] ZHANG W Z, YUAN J, YU Z, et al. Study of the global behavior of wireless sensor networks based on celluar automata[J]. Acta Physica Sinica, 2008, 57(1): 6897-6900.

[6] YUAN J, REN Y, SHAN M. Investigation of a Cellular Automaton model for computer network[J]. Chin Phys Soc, 2000, 49(3): 399-402, 1986.

[7] WOLFRAM S. Statistical mechanics of cellular automata[J]. Reviews of Modern Physics, 1983, 55(3): 601-644.

[8] WOLFRAM S. Theory and applications of cellular automata[M]. Singapore: World Scientific Publication, 1986.

編輯張 俊

CA-Based Energy-Efficient Routing Protocol for WSN

YU Qin, WANG Wei-dong, LENG Su-peng, and MAO Yu-ming
(Key Laboratory of Optical Fiber Sensing and Communications of the Ministry of Education, University of Electronic Science and Technology of China Chengdu 611731)

In this paper a cellular automata (CA) -based energy efficient routing protocol for wireless sensor network (WSN) is proposed to reduce the energy consumption of the wireless sensor nodes in the WSN. The wireless sensor nodes are self-organized to a multi-level CA area around the sink node. According to the CA message the sink node determines the state change of other wireless sensor nodes to realize the energy conservation. Simulation results demonstrate that the proposed routing protocol can reduce the network energy consumption, improve the energy utilization rate, and prolong the network life span.

CA; energy efficient; routing protocol; wireless sensor network

TP919

A doi:10.3969/j.issn.1001-0548.2015.04.007

2013 ? 08 ? 06；

2015 ? 02 ? 04

國家自然科學基金(61104042)；中央高?；究蒲袠I務費專項資金(ZYGX2011J005)；成都市科技惠民項目(2014-HM01-00310-S'F)

于秦(1974 ? )，女，博士，副教授，主要從事無線網絡、移動通信和信息安全方面的研究.