基于元胞自動(dòng)機(jī)的無(wú)線傳感網(wǎng)路由節(jié)能技術(shù)

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

(電子科技大學(xué)光纖傳感與通信教育部重點(diǎn)實(shí)驗(yàn)室 成都 611731)

基于元胞自動(dòng)機(jī)的無(wú)線傳感網(wǎng)路由節(jié)能技術(shù)

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

(電子科技大學(xué)光纖傳感與通信教育部重點(diǎn)實(shí)驗(yàn)室 成都 611731)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)(WSN)路由協(xié)議設(shè)計(jì)需首要解決的節(jié)能問(wèn)題，提出一種將元胞自動(dòng)機(jī)(CA)用于無(wú)線傳感器網(wǎng)絡(luò)的高效節(jié)能機(jī)制。該機(jī)制在路由層設(shè)置元胞處理模塊，通過(guò)路由報(bào)文捎帶CA信息網(wǎng)絡(luò)節(jié)點(diǎn)自組織形成以sink節(jié)點(diǎn)為中心的多級(jí)元胞自動(dòng)機(jī)區(qū)域，決策節(jié)點(diǎn)根據(jù)通信過(guò)程中攜帶的元胞信息切換傳感節(jié)點(diǎn)的工作狀態(tài)以實(shí)現(xiàn)節(jié)能。仿真結(jié)果驗(yàn)證了該機(jī)制能降低網(wǎng)絡(luò)整體能量消耗，提高能量利用率，延長(zhǎng)整個(gè)網(wǎng)絡(luò)生存周期。

元胞自動(dòng)機(jī); 節(jié)能; 路由; 無(wú)線傳感器網(wǎng)絡(luò)

無(wú)線傳感器網(wǎng)絡(luò)(WSN)是一種涉及多學(xué)科的新型無(wú)線網(wǎng)絡(luò)。它綜合了傳感器技術(shù)、網(wǎng)絡(luò)通信技術(shù)、無(wú)線傳輸技術(shù)、嵌入式計(jì)算技術(shù)、軟件編程等技術(shù)，是通信和計(jì)算機(jī)科學(xué)的一個(gè)研究熱點(diǎn)領(lǐng)域。WSN網(wǎng)絡(luò)通常部署在自然環(huán)境復(fù)雜的區(qū)域，節(jié)點(diǎn)的供電非常有限。因此如何在保證數(shù)據(jù)傳輸可靠性沒(méi)有明顯降低的情況下，盡量減少節(jié)點(diǎn)能耗是目前研究的主要方向之一。

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

本文基于元胞自動(dòng)機(jī)機(jī)制，在路由層設(shè)置元胞處理模塊(CA-modular)，通過(guò)路由報(bào)文中捎帶CA信息，網(wǎng)絡(luò)節(jié)點(diǎn)自組織形成以sink節(jié)點(diǎn)為中心的多級(jí)元胞自動(dòng)機(jī)區(qū)域。sink節(jié)點(diǎn)元胞處理模塊根據(jù)CA信息和狀態(tài)轉(zhuǎn)換機(jī)制決策是否應(yīng)使某些子節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。休眠節(jié)點(diǎn)定時(shí)器超時(shí)時(shí)，節(jié)點(diǎn)恢復(fù)工作狀態(tài)。該機(jī)制能降低無(wú)線傳感網(wǎng)絡(luò)整體能量消耗，提高能量利用率，延長(zhǎng)整個(gè)網(wǎng)絡(luò)生存時(shí)間。

1 無(wú)線傳感網(wǎng)絡(luò)的元胞自動(dòng)機(jī)模擬

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

無(wú)線傳感網(wǎng)絡(luò)由大量分布式的微小傳感器節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)只能與周圍臨近的節(jié)點(diǎn)進(jìn)行通信，并依靠局部信息做出行為決策。而元胞自動(dòng)機(jī)能夠以簡(jiǎn)單的規(guī)則揭示復(fù)雜的全局特性，并且結(jié)構(gòu)簡(jiǎn)單、易于計(jì)算機(jī)實(shí)現(xiàn)。因此，本文首先構(gòu)建面向無(wú)線傳感網(wǎng)絡(luò)的二維元胞自動(dòng)機(jī)模型。該模型建立二維元胞自動(dòng)機(jī)與實(shí)際無(wú)線傳感網(wǎng)絡(luò)的映射關(guān)系，包括元胞空間與節(jié)點(diǎn)空間、元胞鄰居集與節(jié)點(diǎn)鄰居集、元胞狀態(tài)集與節(jié)點(diǎn)狀態(tài)集、元胞狀態(tài)轉(zhuǎn)換規(guī)則與節(jié)點(diǎn)狀態(tài)更新等要素間的對(duì)應(yīng)關(guān)系。

考慮一個(gè)平面分布的無(wú)線傳感器網(wǎng)絡(luò)，N個(gè)靜態(tài)獨(dú)立的傳感節(jié)點(diǎn)以隨機(jī)的方式布撒在一個(gè)包含L×L個(gè)格子單元的規(guī)則二維網(wǎng)格中，網(wǎng)格即代表一個(gè)二維元胞空間。為簡(jiǎn)化分析，假設(shè)一個(gè)網(wǎng)格單元至多包含一個(gè)傳感節(jié)點(diǎn)，這個(gè)平面無(wú)線傳感網(wǎng)即構(gòu)成元胞空間，一個(gè)傳感節(jié)點(diǎn)就是元胞空間中的一個(gè)元胞。任何節(jié)點(diǎn)在空間中的位置可以用該二維網(wǎng)格中的水平坐標(biāo)i和垂直坐標(biāo)j唯一標(biāo)識(shí)。記C(i,j)表示處于(i,j)坐標(biāo)的節(jié)點(diǎn)或元胞。元胞空間記為：

由于信號(hào)強(qiáng)度路徑衰減，每個(gè)節(jié)點(diǎn)存在最大通信距離Rc，二維元胞模型中的鄰居定義由該最大通信距離決定。定義節(jié)點(diǎn)鄰域?yàn)镸oore型結(jié)構(gòu)，定義節(jié)點(diǎn)C(i,j)的通信鄰居集合為：

本文考慮傳感器節(jié)點(diǎn)采用S-MAC協(xié)議，即每個(gè)節(jié)點(diǎn)在每個(gè)round周期按照工作與休眠兩個(gè)階段的方式工作。節(jié)點(diǎn)根據(jù)喚醒規(guī)則選擇自己處于工作狀態(tài)或休眠狀態(tài)。當(dāng)處于工作狀態(tài)時(shí)，節(jié)點(diǎn)則對(duì)周圍環(huán)境進(jìn)行檢測(cè)并進(jìn)行必要的處理；而處于休眠狀態(tài)時(shí)，節(jié)點(diǎn)將進(jìn)入休眠狀態(tài)以節(jié)省能量。因而可以定義k=2，S={1,0}?！?”狀態(tài)表示節(jié)點(diǎn)工作；“0”狀態(tài)表示節(jié)點(diǎn)休眠。

對(duì)于任意節(jié)點(diǎn)C(i, j)，按照狀態(tài)轉(zhuǎn)移規(guī)則有:

即1t+時(shí)刻的節(jié)點(diǎn)狀態(tài)是由t時(shí)刻該節(jié)點(diǎn)鄰居狀態(tài)按照一定規(guī)則f(?)確定的。

2 基于多級(jí)分區(qū)元胞自動(dòng)機(jī)的多跳無(wú)線傳感網(wǎng)絡(luò)路由節(jié)能技術(shù)

無(wú)線傳感器網(wǎng)絡(luò)中隨機(jī)散布的sensor傳感器節(jié)點(diǎn)以自組織形式構(gòu)成網(wǎng)絡(luò)，通過(guò)多跳中繼方式將監(jiān)測(cè)數(shù)據(jù)傳到sink節(jié)點(diǎn)。本文的無(wú)線傳感網(wǎng)絡(luò)拓?fù)湫问綖樾切?，由一個(gè)中心sink節(jié)點(diǎn)和若干sensor傳感器節(jié)點(diǎn)組成。sensor傳感器節(jié)點(diǎn)為同質(zhì)性節(jié)點(diǎn)，具有數(shù)據(jù)采集和數(shù)據(jù)中繼功能，所有sensor傳感器節(jié)點(diǎn)將數(shù)據(jù)傳輸至中心sink節(jié)點(diǎn)。中心sink節(jié)點(diǎn)能量無(wú)限且一直處于工作狀態(tài)。只有中心sink節(jié)點(diǎn)有決策休眠功能，即sensor節(jié)點(diǎn)的休眠或工作狀態(tài)由中心sink節(jié)點(diǎn)控制。

圖1 基于多級(jí)分區(qū)元胞自動(dòng)機(jī)的多跳WSN

sensor節(jié)點(diǎn)啟動(dòng)后，以sink節(jié)點(diǎn)為邏輯中心自組織形成多個(gè)元胞自動(dòng)機(jī)CA區(qū)域，如圖1所示。CA區(qū)域共包括3種等級(jí)節(jié)點(diǎn)。中心sink節(jié)點(diǎn)為零級(jí)節(jié)點(diǎn)，sink節(jié)點(diǎn)單跳通信范圍內(nèi)的sensor傳感器節(jié)點(diǎn)為第一級(jí)節(jié)點(diǎn)，第一級(jí)節(jié)點(diǎn)單跳通信范圍內(nèi)的sensor傳感器節(jié)點(diǎn)為第二級(jí)節(jié)點(diǎn)。sensor節(jié)點(diǎn)的通信級(jí)別至多兩級(jí)。節(jié)點(diǎn)啟動(dòng)時(shí)不具有等級(jí)信息，通過(guò)CA區(qū)域構(gòu)建過(guò)程確定節(jié)點(diǎn)等級(jí)，且僅具有唯一一種等級(jí)。數(shù)據(jù)傳輸過(guò)程中，第二級(jí)節(jié)點(diǎn)傳輸數(shù)據(jù)經(jīng)第一級(jí)節(jié)點(diǎn)至sink節(jié)點(diǎn)。

在CA區(qū)域的構(gòu)建完成后，每間隔一段時(shí)間，sink節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)(第一級(jí)節(jié)點(diǎn))的能量狀態(tài)信息，選擇部分能量較低的節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，鄰居節(jié)點(diǎn)收到休眠通告后轉(zhuǎn)發(fā)給下屬的第二級(jí)節(jié)點(diǎn)并進(jìn)入休眠狀態(tài)。節(jié)點(diǎn)休眠前設(shè)置休眠定時(shí)器，當(dāng)休眠定時(shí)器超時(shí)時(shí)，恢復(fù)工作狀態(tài)。

圖2 協(xié)議棧

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

2.1 CA區(qū)域構(gòu)建

CA區(qū)域構(gòu)建過(guò)程中的報(bào)文交互如圖3所示，構(gòu)建步驟如下所述。

圖3 CA區(qū)域構(gòu)建的報(bào)文交互過(guò)程

1) sink節(jié)點(diǎn)和sensor節(jié)點(diǎn)開機(jī)。sink節(jié)點(diǎn)查詢本地CA表，CA表記錄了鄰居節(jié)點(diǎn)的節(jié)點(diǎn)ID、節(jié)點(diǎn)等級(jí)和剩余能量信息。若CA表為空則觸發(fā)CA區(qū)域構(gòu)建過(guò)程。

2) sink節(jié)點(diǎn)將CA構(gòu)建信息(報(bào)文頭部的信息類型字段為Type_CA_start類型)置于目的地址為廣播的路由報(bào)文中發(fā)送(如AODV路由協(xié)議中的request類型和hello類型報(bào)文)，發(fā)起CA區(qū)域構(gòu)建。定義該類報(bào)文為CA_start。

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

4) sink節(jié)點(diǎn)收到CA_response報(bào)文后，記錄該節(jié)點(diǎn)IP、級(jí)別和能量等信息于自身CA表中。

5) 無(wú)級(jí)別的sensor節(jié)點(diǎn)收到CA_startsecond類型報(bào)文時(shí)，將自身節(jié)點(diǎn)的類型定義為第二級(jí)節(jié)點(diǎn)，構(gòu)建報(bào)文CA_response，發(fā)送給源節(jié)點(diǎn)。一個(gè)已經(jīng)有級(jí)別的sensor節(jié)點(diǎn)再收到CA_start或CA_startsecond類型報(bào)文時(shí)，若自身級(jí)別小于構(gòu)建報(bào)文級(jí)別時(shí)(CA_start為第一級(jí)報(bào)文，CA_startsecond為第二級(jí)報(bào)文)，將放棄原級(jí)別，改為新級(jí)別，即某區(qū)域的第二級(jí)節(jié)點(diǎn)可以變?yōu)槠渌麉^(qū)域的第一級(jí)節(jié)點(diǎn)。

6) 若某節(jié)點(diǎn)處于sink節(jié)點(diǎn)兩跳通信范圍以外則有可能無(wú)法成為任何節(jié)點(diǎn)的子節(jié)點(diǎn)，這種類型的節(jié)點(diǎn)被稱為無(wú)等級(jí)節(jié)點(diǎn)。無(wú)等級(jí)節(jié)點(diǎn)不能進(jìn)入休眠狀態(tài)。因此在網(wǎng)絡(luò)部署時(shí)應(yīng)盡量保證各CA區(qū)域范圍之和能覆蓋全部節(jié)點(diǎn)。至此，CA區(qū)域構(gòu)建完成。

2.2 轉(zhuǎn)換規(guī)則設(shè)計(jì)

無(wú)線傳感器網(wǎng)絡(luò)對(duì)于待檢測(cè)區(qū)域采取冗余配置的方式，使用多個(gè)傳感節(jié)點(diǎn)對(duì)同一區(qū)域或目標(biāo)進(jìn)行檢測(cè)，保證數(shù)據(jù)采集可靠性。對(duì)同一區(qū)域或目標(biāo)的檢測(cè)通常是重復(fù)性的，因此在保證可靠傳輸?shù)幕A(chǔ)上，使部分冗余節(jié)點(diǎn)進(jìn)入休眠狀態(tài)以節(jié)省能量是必要且有效的。

本文定義的轉(zhuǎn)換規(guī)則如下：除sink節(jié)點(diǎn)外的其他節(jié)點(diǎn)取0/1兩種狀態(tài)，分別代表休眠和工作狀態(tài)。sink節(jié)點(diǎn)根據(jù)當(dāng)前狀態(tài)和狀態(tài)轉(zhuǎn)換規(guī)則決策部分子節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。子節(jié)點(diǎn)進(jìn)入休眠狀態(tài)前，通告其自身的所有子節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。節(jié)點(diǎn)進(jìn)入休眠時(shí)設(shè)置休眠定時(shí)器，定時(shí)器超時(shí)時(shí)節(jié)點(diǎn)恢復(fù)工作狀態(tài)。

影響sink節(jié)點(diǎn)決策休眠的因素主要體現(xiàn)在無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)冗余配置情況和節(jié)點(diǎn)的剩余能量?jī)蓚€(gè)方面，可表示為：

式中，N_sleep表示可以休眠的節(jié)點(diǎn)數(shù)：R表示冗余率；N表示網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)；k為冗余節(jié)點(diǎn)中進(jìn)入休眠狀態(tài)的節(jié)點(diǎn)比例。

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)冗余配置情況將影響休眠決策，由式(5)可見(jiàn)，sink節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)冗余率R計(jì)算鄰居節(jié)點(diǎn)中冗余節(jié)點(diǎn)個(gè)數(shù)，判定冗余節(jié)點(diǎn)個(gè)數(shù)的k%進(jìn)入休眠狀態(tài)。此外，節(jié)點(diǎn)剩余能量將影響休眠決策。每個(gè)第二級(jí)sensor節(jié)點(diǎn)定時(shí)向第一級(jí)sensor節(jié)點(diǎn)匯報(bào)能量情況，第一級(jí)sensor將自身能量和所有第二級(jí)sensor 節(jié)點(diǎn)能量計(jì)算平均值后，發(fā)送給sink節(jié)點(diǎn)。sink節(jié)點(diǎn)記錄第一級(jí)sensor節(jié)點(diǎn)通告的剩余能量情況。

2.3 休眠與喚醒過(guò)程

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

子節(jié)點(diǎn)收到休眠通告報(bào)文后同樣完成上述過(guò)程。第二級(jí)節(jié)點(diǎn)不能發(fā)送休眠通告報(bào)文。無(wú)等級(jí)節(jié)點(diǎn)不能進(jìn)入休眠狀態(tài)，因此在網(wǎng)絡(luò)部署時(shí)應(yīng)盡量保證各CA區(qū)域范圍之和能覆蓋全部節(jié)點(diǎn)。

本文定義休眠/喚醒周期時(shí)長(zhǎng)為2倍休眠定時(shí)器持續(xù)時(shí)間，用以避免節(jié)點(diǎn)頻繁地在工作和休眠狀態(tài)之間切換，從而保證網(wǎng)絡(luò)的穩(wěn)定性。sink節(jié)點(diǎn)在每個(gè)休眠/喚醒周期對(duì)子節(jié)點(diǎn)進(jìn)行一次狀態(tài)轉(zhuǎn)換決策。

3 仿真及結(jié)果分析

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

仿真拓?fù)浞謩e設(shè)置為55×格狀拓?fù)浜?7×格狀拓?fù)?，如圖4所示。在55×格狀拓?fù)渲?，拓?fù)渲行挠?個(gè)sink節(jié)點(diǎn)接收傳感數(shù)據(jù)和決策休眠；77×格狀拓?fù)?，在拓?fù)渲杏?個(gè)sink節(jié)點(diǎn)接收傳感數(shù)據(jù)、劃分CA區(qū)域和決策休眠。拓?fù)浞礁裰蠭代表在CA區(qū)域劃分后成為第一級(jí)節(jié)點(diǎn)，II代表將成為第二級(jí)節(jié)點(diǎn)，none代表將成為無(wú)等級(jí)節(jié)點(diǎn)。每一個(gè)CA區(qū)域以sink節(jié)點(diǎn)為中心，其邊緣節(jié)點(diǎn)可能是第二級(jí)節(jié)點(diǎn)也可能是第一級(jí)節(jié)點(diǎn)。每一個(gè)節(jié)點(diǎn)只存在于一個(gè)CA區(qū)域中，不會(huì)存在區(qū)域重疊節(jié)點(diǎn)。表1為仿真參數(shù)設(shè)置。

表1 仿真參數(shù)設(shè)置

圖4 仿真拓?fù)?/p>

圖5為55×拓?fù)浜?7×拓?fù)涞恼w能量消耗。在此過(guò)程中節(jié)點(diǎn)能量無(wú)限。能量消耗包括傳感節(jié)點(diǎn)發(fā)送、接收和偵聽過(guò)程中的能量消耗。節(jié)點(diǎn)從第50 s開始發(fā)送傳感數(shù)據(jù)。采用CA機(jī)制后，節(jié)點(diǎn)首先完成CA區(qū)域構(gòu)建，然后sink可以根據(jù)節(jié)點(diǎn)工作狀態(tài)決策部分節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，因此，降低了整體能量消耗。對(duì)55×拓?fù)浜?7×拓?fù)?，總能量消耗大致分別減少了10%～30%。

圖5 整體能量消耗圖

圖6比較了兩種網(wǎng)絡(luò)的能量利用率。t時(shí)刻的能量利用率為t時(shí)刻以前傳輸數(shù)據(jù)報(bào)文所消耗的總能量與t時(shí)刻以前傳輸所有報(bào)文所消耗的總能量之比。由圖6可見(jiàn)，采用CA機(jī)制后能量利用率提高了10%～20%。并且節(jié)點(diǎn)數(shù)少時(shí)，能量利用率高于節(jié)點(diǎn)數(shù)多時(shí)的能量利用率。分析其原因在于，當(dāng)節(jié)點(diǎn)數(shù)增多時(shí)，在路由等方面的開銷更多，CA區(qū)域構(gòu)建過(guò)程更復(fù)雜，時(shí)間更長(zhǎng)，導(dǎo)致能量利用率下降。通過(guò)使用CA處理機(jī)制，使節(jié)點(diǎn)在合適的情況下休眠，可以降低網(wǎng)絡(luò)沖突，減少空閑偵聽和沖突重傳帶來(lái)的開銷，從而提高能量利用率。

圖6 能量利用率

在圖7中，限制每個(gè)節(jié)點(diǎn)的能量上限為4 J，在正常工作模式下約可以工作500 s。由于不同節(jié)點(diǎn)的負(fù)載不同，負(fù)載重的節(jié)點(diǎn)能量消耗快，負(fù)載輕的節(jié)點(diǎn)能量消耗相對(duì)慢一些，所以不是所有節(jié)點(diǎn)在同一時(shí)刻能量耗盡，而是整個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)能量逐漸耗盡。由圖7可見(jiàn)，采用CA機(jī)制后節(jié)點(diǎn)生存時(shí)間明顯變長(zhǎng)，節(jié)點(diǎn)能量耗盡速度明顯下降，整個(gè)網(wǎng)絡(luò)的生存期得到提高。

圖8展示了兩種拓?fù)湎虏捎肅A機(jī)制和未采用CA機(jī)制的傳輸率對(duì)比。t時(shí)刻的傳輸率為t時(shí)刻以前PAN節(jié)點(diǎn)收到的數(shù)據(jù)報(bào)文個(gè)數(shù)與t時(shí)刻以前傳感節(jié)點(diǎn)發(fā)送的數(shù)據(jù)報(bào)文個(gè)數(shù)之比。傳輸率能夠從整體上準(zhǔn)確反映網(wǎng)絡(luò)傳輸可靠性。由圖8可見(jiàn)，網(wǎng)絡(luò)運(yùn)行初期，采用CA機(jī)制與未采用CA機(jī)制的傳輸率均在80%以上，能夠保證傳輸可靠性，滿足用戶的可靠性需求。隨著節(jié)點(diǎn)能量的消耗，未采用CA機(jī)制的網(wǎng)絡(luò)的傳輸率明顯下降，逐漸下降至80%以下。節(jié)點(diǎn)采用CA機(jī)制后，sink節(jié)點(diǎn)協(xié)調(diào)部分節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，保證了網(wǎng)絡(luò)的整體穩(wěn)定性。開啟CA機(jī)制后，曲線出現(xiàn)交疊現(xiàn)象的一個(gè)原因是節(jié)點(diǎn)在休眠和工作狀態(tài)進(jìn)行切換，影響了數(shù)據(jù)傳輸路徑和可靠性。某時(shí)刻進(jìn)入休眠狀態(tài)的節(jié)點(diǎn)多，網(wǎng)絡(luò)傳輸率下降; 某時(shí)刻進(jìn)入休眠狀態(tài)的節(jié)點(diǎn)少，網(wǎng)絡(luò)傳輸率上升，從而使曲線在一定范圍內(nèi)浮動(dòng)。而對(duì)于未開啟CA機(jī)制的網(wǎng)絡(luò)，隨著路由的建立，整體網(wǎng)絡(luò)趨于穩(wěn)定，從而傳輸率基本穩(wěn)定。

圖7 節(jié)點(diǎn)生存時(shí)間

圖8 傳輸率

4 結(jié) 論

本文提出了一種基于多級(jí)分區(qū)元胞自動(dòng)機(jī)的多跳無(wú)線傳感器網(wǎng)絡(luò)路由節(jié)能技術(shù)。通過(guò)設(shè)計(jì)元胞自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換規(guī)則，中心sink節(jié)點(diǎn)選擇部分剩余能量低的sensor節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，從而使得節(jié)點(diǎn)能夠通過(guò)元胞自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換規(guī)則，在休眠和工作狀態(tài)間進(jìn)行切換。剩余能量等信息隨路由報(bào)文傳輸，無(wú)需增加額外的開銷。本文的休眠決策機(jī)制通過(guò)合理使用元胞自動(dòng)機(jī)處理機(jī)制，在網(wǎng)絡(luò)層的路由協(xié)議中添加CA處理模塊，在保證網(wǎng)絡(luò)傳輸可靠性的基礎(chǔ)上，減少了節(jié)點(diǎn)能量消耗。仿真驗(yàn)證了使用CA處理機(jī)制在網(wǎng)絡(luò)傳輸率沒(méi)有大幅下降的前提下，在減少能量消耗、延長(zhǎng)網(wǎng)絡(luò)生存期和提高能量利用率上的良好效果。在后續(xù)研究中，將進(jìn)一步對(duì)基于元胞自動(dòng)機(jī)的無(wú)線傳感網(wǎng)絡(luò)節(jié)能問(wèn)題展開更深入研究。針對(duì)具有自組織特性的無(wú)線傳感網(wǎng)絡(luò)時(shí)空演化規(guī)律，研究如何在盡量減少系統(tǒng)能量消耗的前提下，保證無(wú)線傳感網(wǎng)絡(luò)拓?fù)涞倪B通性和覆蓋性。

[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

國(guó)家自然科學(xué)基金(61104042)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(ZYGX2011J005)；成都市科技惠民項(xiàng)目(2014-HM01-00310-S'F)

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