一種基于元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂品椒?

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

(1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院，南京 210003； 2.南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京 210093； 3.江蘇省無(wú)線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，南京 210003； 4.寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，南京 210003； 5.蘇州出入境檢驗(yàn)檢疫局，江蘇蘇州 215104)

無(wú)線傳感器網(wǎng)絡(luò)是一種由大量傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線方式協(xié)作地檢測(cè)、感知和處理各種環(huán)境或者檢測(cè)對(duì)象信息的網(wǎng)絡(luò)系統(tǒng)［1－3］，傳感器網(wǎng)絡(luò)節(jié)點(diǎn)通常由電池供電，通信、計(jì)算、處理能力有限，對(duì)該網(wǎng)絡(luò)進(jìn)行拓?fù)淇刂频哪繕?biāo)是尋找一種節(jié)點(diǎn)的配置方法，在減少系統(tǒng)能量消耗的前提下，保證整個(gè)網(wǎng)絡(luò)拓?fù)涞倪B通性和覆蓋性。

元胞自動(dòng)機(jī)(Cellular automata)作為狀態(tài)離散系統(tǒng)，能夠以簡(jiǎn)單的規(guī)則揭示復(fù)雜的全局特性，因而成為研究自組織時(shí)空演化規(guī)律的重要工具［4］。文獻(xiàn)［5］將元胞自動(dòng)機(jī)作為一種模擬無(wú)線傳感器網(wǎng)絡(luò)行為的工具，認(rèn)為無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)之間具有的高度協(xié)作性，形成類似于元胞自動(dòng)機(jī)所模擬的大部分動(dòng)力學(xué)系統(tǒng)。文獻(xiàn)［6］在無(wú)線傳感器網(wǎng)絡(luò)的元胞自動(dòng)機(jī)模型基礎(chǔ)上，提出一種節(jié)點(diǎn)可動(dòng)態(tài)調(diào)節(jié)通信范圍的方法。文獻(xiàn)［7］通過(guò)建立無(wú)線傳感器網(wǎng)絡(luò)的二維元胞自動(dòng)機(jī)模型，分析節(jié)點(diǎn)狀態(tài)規(guī)則和網(wǎng)絡(luò)拓?fù)涓采w性與連通性的關(guān)系，并將無(wú)線傳感器網(wǎng)絡(luò)的整體拓?fù)涮匦猿醪綒w納為震蕩、衰減、穩(wěn)定等基本模式。

上述研究將無(wú)線傳感器網(wǎng)絡(luò)平面看成是按照正方形網(wǎng)絡(luò)排列的二維元胞空間，每個(gè)格點(diǎn)對(duì)應(yīng)一個(gè)傳感器節(jié)點(diǎn)，具有工作和休眠兩種狀態(tài)。鄰居定義為與元胞相鄰的8個(gè)元胞，即Moore型鄰居［8］。每個(gè)元胞根據(jù)鄰居狀態(tài)的變化改變自身狀態(tài)。通常情況下，傳感器節(jié)點(diǎn)由隨機(jī)散布方式部署，并非規(guī)則分布，并且節(jié)點(diǎn)自身能量有限，隨著網(wǎng)絡(luò)的運(yùn)行，可能因?yàn)槟芰亢谋M而失效。因此，本文在此基礎(chǔ)上擴(kuò)展元胞狀態(tài)為3種，即元胞處無(wú)節(jié)點(diǎn)對(duì)應(yīng)/節(jié)點(diǎn)失效、節(jié)點(diǎn)休眠、節(jié)點(diǎn)工作，元胞以隨機(jī)方式部署，尋找元胞最優(yōu)狀態(tài)演化規(guī)則，以實(shí)現(xiàn)在保證網(wǎng)絡(luò)覆蓋率和連通度的前提下減少能耗。

1 基于元胞自動(dòng)機(jī)的拓?fù)淇刂颇Ｐ?/h2>

1.1 元胞自動(dòng)機(jī)模型

以Conway的生命游戲［9］為例，生命游戲描述的是生物群體的生存繁殖規(guī)律:在生命密度過(guò)小時(shí)，由于孤單使生物體缺乏配種繁殖機(jī)會(huì)、缺乏互助導(dǎo)致生命危機(jī)，生物體由生變?yōu)樗?；在生命密度過(guò)大，由于資源缺乏、相互競(jìng)爭(zhēng)也會(huì)出現(xiàn)生存危機(jī)，生物體也由生變?yōu)樗溃恢挥刑幱趥€(gè)體適中狀態(tài)的生物才能生存并繁衍后代［4］。

用元胞自動(dòng)機(jī)模型表示為:

(1)元胞分布于規(guī)則劃分的二維網(wǎng)格上；

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

(3)元胞的狀態(tài)由上一時(shí)刻自身的狀態(tài)和鄰居狀態(tài)決定，鄰居為與元胞相鄰的8個(gè)元胞；

(4)演化規(guī)則用數(shù)學(xué)表示為S23/B3，即:

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

無(wú)線傳感器網(wǎng)絡(luò)運(yùn)行狀態(tài)類似于生命游戲，如果利用網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行監(jiān)測(cè)會(huì)產(chǎn)生冗余，也就是說(shuō)，在同一時(shí)刻會(huì)有2個(gè)或2個(gè)以上的節(jié)點(diǎn)監(jiān)測(cè)同一個(gè)區(qū)域，不僅浪費(fèi)能源，而且在傳輸數(shù)據(jù)包的過(guò)程中會(huì)產(chǎn)生碰撞和阻塞；如果節(jié)點(diǎn)周圍鄰居過(guò)少，那么節(jié)點(diǎn)也會(huì)因?yàn)樨?fù)載過(guò)大、能量耗盡而失效。因此節(jié)點(diǎn)的工作/休眠機(jī)制成為節(jié)省能耗、延長(zhǎng)網(wǎng)絡(luò)壽命的一種有效手段。工作/休眠機(jī)制即在合適的時(shí)間［10－13］關(guān)閉節(jié)點(diǎn)發(fā)射器，讓其進(jìn)入睡眠狀態(tài)，以大幅減小能量消耗。

本文考慮無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)經(jīng)部署初始化后有三種狀態(tài):工作、休眠、失效(或空位)。傳感器節(jié)點(diǎn)具有固定的工作/休眠周期，即當(dāng)工作(休眠)一定時(shí)間T后進(jìn)入休眠(工作)狀態(tài)。每個(gè)傳感器節(jié)點(diǎn)具有一定的初始能量E0，當(dāng)處于工作狀態(tài)時(shí)，打開發(fā)射器進(jìn)行接收、轉(zhuǎn)發(fā)、監(jiān)聽等操作，因此需要消耗大量的能量Ew，當(dāng)其處于休眠狀態(tài)時(shí)，關(guān)閉發(fā)射器進(jìn)入低功率狀態(tài)，消耗較少的能量Es，隨著網(wǎng)絡(luò)的運(yùn)行，節(jié)點(diǎn)工作、休眠狀態(tài)交替改變，能量耗盡，節(jié)點(diǎn)失效，則節(jié)點(diǎn)狀態(tài)變?yōu)槭?。由于該方法隨機(jī)性較大，可能隨著部分節(jié)點(diǎn)的失效導(dǎo)致網(wǎng)絡(luò)的覆蓋率、連通度下降，影響網(wǎng)絡(luò)的整體性能。因此，需要節(jié)點(diǎn)之間具有高度的協(xié)作性，節(jié)點(diǎn)在固定的時(shí)間段檢測(cè)鄰居狀態(tài)，在保證自己監(jiān)測(cè)的區(qū)域內(nèi)已有足夠的節(jié)點(diǎn)監(jiān)測(cè)后再進(jìn)入休眠，同樣，處于休眠狀態(tài)的節(jié)點(diǎn)發(fā)現(xiàn)該區(qū)域內(nèi)工作節(jié)點(diǎn)不足時(shí)，及時(shí)醒過(guò)來(lái)進(jìn)入工作狀態(tài)。

基于二維元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)模型敘述如下:

(1)元胞狀態(tài)集S={0，1，2}，0 表示無(wú)節(jié)點(diǎn)/節(jié)點(diǎn)失效，1表示節(jié)點(diǎn)處于休眠狀態(tài)；2表示節(jié)點(diǎn)處于工作狀態(tài)。

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

(3)每個(gè)元胞的狀態(tài)由上一時(shí)刻鄰居元胞狀態(tài)以及自身狀態(tài)決定。具體演化規(guī)則如下:

如果元胞在t時(shí)刻為2，且其鄰居狀態(tài)為2的個(gè)數(shù)為Ni，那么t+Δt時(shí)刻元胞狀態(tài)不變；

如果元胞在t時(shí)刻為1，且其鄰居狀態(tài)為2的個(gè)數(shù)為Nj，那么t+Δt時(shí)刻元胞狀態(tài)改變?yōu)?。

上述規(guī)則中:Δt表示一個(gè)時(shí)間間隔；Ni和Nj是選擇最優(yōu)演化規(guī)則的兩個(gè)常量，表示最佳鄰居節(jié)點(diǎn)個(gè)數(shù)。

2 基于元胞自動(dòng)機(jī)的拓?fù)淇刂品椒?/h2>

2.1 方法流程

根據(jù)無(wú)線傳感器網(wǎng)絡(luò)的元胞自動(dòng)機(jī)模型，可以建立基于元胞自動(dòng)機(jī)的拓?fù)淇刂品椒?，首先做兩點(diǎn)假設(shè):

(1)假設(shè)傳感器網(wǎng)絡(luò)為同質(zhì)網(wǎng)絡(luò)，即所有節(jié)點(diǎn)的大小、形狀、結(jié)構(gòu)以及具有的初始能量相同。

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

在上述假設(shè)條件下，基于元胞自動(dòng)機(jī)的拓?fù)淇刂屏鞒倘缦?

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

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

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

上述流程中，規(guī)模L、節(jié)點(diǎn)個(gè)數(shù)N、時(shí)間間隔Δt、工作/休眠周期T、元胞初始能量E0、工作狀態(tài)消耗能量Ew、休眠狀態(tài)消耗能量Es等參數(shù)可根據(jù)實(shí)際應(yīng)用情況進(jìn)行選擇。

2.2 評(píng)價(jià)參數(shù)

為評(píng)價(jià)基于元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂品椒ㄐ阅?，定義如下二維元胞模型的拓?fù)涮匦?

(1)覆蓋率

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

令一個(gè)節(jié)點(diǎn)的覆蓋概率為p(A)=p，那么兩個(gè)節(jié)點(diǎn)的覆蓋概率為

依次，n個(gè)節(jié)點(diǎn)的覆蓋概率為

(2)連通度

無(wú)線傳感器網(wǎng)絡(luò)作為信息收集系統(tǒng)，需要實(shí)現(xiàn)多跳的信息傳輸，在元胞自動(dòng)機(jī)模型中表現(xiàn)為活著的元胞擁有活著的鄰居［6］。處于工作狀態(tài)元胞的鄰居中無(wú)處于工作狀態(tài)的元胞，則對(duì)網(wǎng)絡(luò)連通率的貢獻(xiàn)為0。所以，連通度表示為區(qū)域內(nèi)(所有工作節(jié)點(diǎn)個(gè)數(shù)－鄰居節(jié)點(diǎn)未處于工作狀態(tài)的工作節(jié)點(diǎn)個(gè)數(shù))/所有工作節(jié)點(diǎn)個(gè)數(shù)。

(3)能耗指數(shù)

某一時(shí)刻工作節(jié)點(diǎn)占所有節(jié)點(diǎn)的比重表示網(wǎng)絡(luò)該時(shí)刻的能耗指數(shù)。能耗指數(shù)越高，說(shuō)明該時(shí)刻工作節(jié)點(diǎn)個(gè)數(shù)越多，能量消耗越大。

3 仿真分析

我們利用MATLAB進(jìn)行仿真研究，定義元胞自動(dòng)機(jī)的規(guī)模為L(zhǎng)，初始元胞總數(shù)為L(zhǎng)2，試驗(yàn)中取L=50。根據(jù)實(shí)際網(wǎng)絡(luò)特點(diǎn)，采用周期性邊界條件。網(wǎng)絡(luò)初始化為隨機(jī)部署750個(gè)元胞，即令30%的元胞狀態(tài)為1，并在所有狀態(tài)為1的元胞中以30%概率取2。元胞半徑R=3。取Δt為1個(gè)時(shí)間步，連續(xù)工作/休眠周期為3個(gè)時(shí)間步，元胞初始能量為0.8 J，每個(gè)時(shí)刻中，工作狀態(tài)消耗能量0.016 5 J，休眠狀態(tài)消耗能量0.000 08 J。仿真研究?jī)蓚€(gè)方面內(nèi)容:①研究在不同的局部更新規(guī)則下，系統(tǒng)的覆蓋率、連通度和能耗指數(shù)的時(shí)間演化特征；②研究基于元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂品椒ㄅc節(jié)點(diǎn)隨機(jī)部署后采用隨機(jī)休眠/工作機(jī)制下的拓?fù)涮匦浴?/p>

3.1 最佳局部更新規(guī)則

在不同的規(guī)則下，系統(tǒng)呈現(xiàn)出復(fù)雜的時(shí)空演化特性。圖1所示為采用S34/B23規(guī)則下的網(wǎng)絡(luò)覆蓋率和連通度的變化情況。從圖1可見，系統(tǒng)的覆蓋率和連通度經(jīng)過(guò)有限次震蕩以后逐步趨于穩(wěn)定，說(shuō)明在此網(wǎng)絡(luò)狀態(tài)下，當(dāng)每個(gè)傳感器節(jié)點(diǎn)處于工作狀態(tài)的鄰居數(shù)為3或4時(shí)，網(wǎng)絡(luò)能夠通過(guò)一定時(shí)間的自適應(yīng)調(diào)節(jié)后保持一個(gè)相對(duì)穩(wěn)定的拓?fù)錉顟B(tài)。當(dāng)處于工作狀態(tài)的鄰居數(shù)大于4或小于3個(gè)時(shí)，測(cè)試顯示覆蓋率和連通度始終處于震蕩狀態(tài)，說(shuō)明網(wǎng)絡(luò)中工作節(jié)點(diǎn)的密度不均衡，造成網(wǎng)絡(luò)覆蓋率和連通度周期震蕩，影響網(wǎng)絡(luò)的整體性能。另外，從圖中可以看出，當(dāng)休眠概率保持在70%左右時(shí)(即保持網(wǎng)絡(luò)中30%的節(jié)點(diǎn)處于工作狀態(tài))，即可保證網(wǎng)絡(luò)具有良好的覆蓋率和連通度。

圖1 規(guī)則S34/B23下網(wǎng)絡(luò)覆蓋率和連通度的變化情況

3.2 基于元胞自動(dòng)機(jī)的拓?fù)淇刂品椒?/h3>

如圖2所示，當(dāng)系統(tǒng)運(yùn)行至100步時(shí)，采用隨機(jī)休眠/工作機(jī)制的網(wǎng)絡(luò)中節(jié)點(diǎn)能量完全耗盡，而基于元胞自動(dòng)機(jī)方法的網(wǎng)絡(luò)中運(yùn)行到110步時(shí)才逐漸有節(jié)點(diǎn)失效，剩余節(jié)點(diǎn)數(shù)開始逐漸減少，基于元胞自動(dòng)機(jī)方法的網(wǎng)絡(luò)壽命比隨機(jī)休眠/工作機(jī)制的網(wǎng)絡(luò)壽命延長(zhǎng)80%左右。

圖2 兩種方法隨時(shí)間變化剩余節(jié)點(diǎn)數(shù)和能耗指數(shù)的變化情況

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

圖3給出節(jié)點(diǎn)休眠概率、覆蓋率和連通度的變化情況。圖3(a)中隨機(jī)工作/休眠機(jī)制節(jié)點(diǎn)休眠，圖3(b)、3(c)所示采用元胞自動(dòng)機(jī)方法的網(wǎng)絡(luò)覆蓋率和連通度有小幅度的震蕩，但基本都在90%左右，說(shuō)明網(wǎng)絡(luò)能夠較好地自適應(yīng)調(diào)整其拓?fù)錉顟B(tài)。相對(duì)于定時(shí)工作/休眠的情況而言，基于元胞自動(dòng)機(jī)的拓?fù)淇刂品椒ㄔ跊]有影響網(wǎng)絡(luò)覆蓋率和連通度的前提下，減少了網(wǎng)絡(luò)系統(tǒng)能耗，延長(zhǎng)了網(wǎng)絡(luò)運(yùn)行壽命。

4 結(jié)束語(yǔ)

拓?fù)淇刂剖茄芯繉?shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)能量高效利用的主要技術(shù)之一，工作/休眠機(jī)制是拓?fù)淇刂蒲芯恐幸粋€(gè)重要的部分。利用元胞自動(dòng)機(jī)對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行建模，有利于研究與控制節(jié)點(diǎn)間相互作用導(dǎo)致的網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化。本文在隨機(jī)休眠/工作機(jī)制的基礎(chǔ)上，提出了一種適用于一般性無(wú)線傳感器網(wǎng)絡(luò)的元胞自動(dòng)機(jī)模型，建立了基于該模型的拓?fù)淇刂品椒?，仿真表明該方法在保證網(wǎng)絡(luò)覆蓋率的前提下減少了能量消耗，延長(zhǎng)了網(wǎng)絡(luò)壽命。

在今后的工作中，我們將結(jié)合更多問(wèn)題，考慮與其他拓?fù)淇刂扑惴ㄟM(jìn)行比較，進(jìn)一步深化元胞自動(dòng)機(jī)在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用。另外，元胞自動(dòng)機(jī)在無(wú)線傳感器網(wǎng)絡(luò)中的應(yīng)用多針對(duì)同質(zhì)網(wǎng)絡(luò)，今后的研究可以擴(kuò)展多層次的元胞自動(dòng)機(jī)模型以實(shí)現(xiàn)異質(zhì)網(wǎng)絡(luò)拓?fù)淇刂啤?/p>

［1］王殊，閻毓杰，胡富平，等.無(wú)線傳感器網(wǎng)絡(luò)的理論及應(yīng)用［M］.北京:北京航空航天大學(xué)出版社，2007.7.

［2］陳志，史倢，章韻，等.基于Agent的無(wú)線傳感器網(wǎng)絡(luò)AUML交互模型［J］.傳感技術(shù)學(xué)報(bào)，2010，23(11):1617－1622.

［3］章韻，王靜玉，陳志，等.基于Q學(xué)習(xí)的無(wú)線傳感器網(wǎng)絡(luò)自組織方法研究［J］.傳感技術(shù)學(xué)報(bào)，2010，23(11):1623－1626.

［4］賈斌，高自友，李克平，等.基于元胞自動(dòng)機(jī)的交通系統(tǒng)建模與模擬［M］.北京:科學(xué)出版社，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］張文鑄，袁堅(jiān)，俞哲，等.基于元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)整體行為研究［J］.物理學(xué)報(bào)，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］石高濤，廖明宏.大規(guī)模傳感器網(wǎng)絡(luò)隨機(jī)睡眠調(diào)度節(jié)能機(jī)制［J］.計(jì)算機(jī)研究與發(fā)展，2006，43(4):579－585.

［14］孫永進(jìn)，孫雨耕，房朝暉.無(wú)線傳感器網(wǎng)絡(luò)的連通與覆蓋［J］.天津大學(xué)學(xué)報(bào)，2005，38(1):14－17.