基于非均勻虛擬網(wǎng)格的無線傳感器網(wǎng)絡(luò)拓?fù)渲貥?gòu)算法

石文玉，鹿建銀

（安徽新華學(xué)院 信息工程學(xué)院，安徽 合肥 230031）

基于非均勻虛擬網(wǎng)格的無線傳感器網(wǎng)絡(luò)拓?fù)渲貥?gòu)算法

石文玉，鹿建銀

（安徽新華學(xué)院 信息工程學(xué)院，安徽 合肥 230031）

拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)研究中一個十分重要的技術(shù)問題.根據(jù)無線傳感器網(wǎng)絡(luò)的通信特點，本文提出了一種采用基于網(wǎng)絡(luò)空間非均勻虛擬網(wǎng)格的方式，旨在復(fù)雜環(huán)境中無線通信遭到破壞時如何快速重建拓?fù)涞姆椒?仿真結(jié)果表明，與傳統(tǒng)算法相比，該算法在通信突然中斷的情況下可以快速恢復(fù)拓?fù)?，并且該算法更適用于大規(guī)模網(wǎng)絡(luò).

拓?fù)淇刂疲粺o線傳感器網(wǎng)絡(luò)；拓?fù)渲貥?gòu)

無線傳感器網(wǎng)絡(luò)（WSN，wireless sensor network）是一種特殊的Adhoc網(wǎng)絡(luò)，由一組低成本、體積小、多功能的傳感器節(jié)點通過自組織方式組成.傳感器節(jié)點間相互協(xié)作感知、采集和處理其覆蓋區(qū)域內(nèi)感知對象的信息，并對其進行處理，發(fā)布給觀察者[1,2].傳感器網(wǎng)絡(luò)具有易部署、自組織、高容錯、可靠性等特點，在諸多領(lǐng)域應(yīng)用前景廣闊.

無線傳感器網(wǎng)絡(luò)（WSN）是由部署在監(jiān)測區(qū)域內(nèi)大量微型傳感器節(jié)點組成，通過無線通信方式形成一種多跳的、自組織的網(wǎng)絡(luò).其主要目的是通過集成化的微型傳感器協(xié)作地對監(jiān)測區(qū)域進行實時監(jiān)測、感知和采集受控對象的狀態(tài)數(shù)據(jù)，如溫度、光強度、噪聲、壓力、運動物體大小、速度和方向等，這些數(shù)據(jù)通過無線方式被發(fā)送并傳送到用戶終端.

1 問題描述

網(wǎng)絡(luò)拓?fù)洌╪etwork topology）是指網(wǎng)絡(luò)中各成員之間特定的物理的即真實的、或邏輯的即虛擬的排列方式[3].在無線傳感器網(wǎng)絡(luò)中，要想每個節(jié)點都能與基站直接通信是不實際的，那么構(gòu)建一個好的網(wǎng)絡(luò)結(jié)構(gòu)，實現(xiàn)終端節(jié)點采集的數(shù)據(jù)通過多跳的方式傳送到基站是非常重要的.

無線傳感器網(wǎng)絡(luò)的基本特點是對基礎(chǔ)設(shè)施要求低，節(jié)點攜帶的能量有限，無線通信易受干擾.無線傳感器網(wǎng)絡(luò)技術(shù)被廣泛應(yīng)用于社會生活的各個角落，例如在軍事、科學(xué)研究、生產(chǎn)等領(lǐng)域，其社會價值巨大.而此項技術(shù)經(jīng)常被應(yīng)用于例如工業(yè)控制、地理環(huán)境、邊境復(fù)雜通信信號覆蓋等多種復(fù)雜環(huán)境下.在上述復(fù)雜環(huán)境中，網(wǎng)絡(luò)的動態(tài)拓?fù)湟捉?jīng)常發(fā)生變化，如何重新迅速建立新的拓?fù)滹@得尤為重要.

本文提出了一種WSN基于非均勻虛擬網(wǎng)格劃分的拓?fù)渲貥?gòu)算法，旨在于網(wǎng)絡(luò)某個或部分節(jié)點的通信遭到破壞后，在短時間內(nèi)迅速恢復(fù)拓?fù)?

2 非均勻虛擬網(wǎng)格劃分

無線傳感器網(wǎng)絡(luò)節(jié)點通過無線信道進行通信，在復(fù)雜環(huán)境下尤其是復(fù)雜電磁環(huán)境下，其通信極易被干擾甚至中斷.節(jié)點所處的地理位置的不同，其所處環(huán)境的電磁環(huán)境由于非人為因素（地形環(huán)境）和人為因素（各種無線電業(yè)務(wù)）而不同[4].依據(jù)網(wǎng)絡(luò)應(yīng)用場景的各個地理位置區(qū)域電磁環(huán)境復(fù)雜度的不同將網(wǎng)絡(luò)劃分為若干個大小不同、相鄰、不重疊且對網(wǎng)絡(luò)能夠全覆蓋的正方形區(qū)域.電磁環(huán)境越復(fù)雜的地區(qū)，被劃分的網(wǎng)格面積越小，而電磁環(huán)境相對較簡單的區(qū)域，網(wǎng)格的面積越大.網(wǎng)絡(luò)中的簇分別在每個網(wǎng)格中產(chǎn)生，這樣非均勻的網(wǎng)格劃分就可以使得在電磁環(huán)境簡單的的區(qū)域簇的數(shù)量少，在電磁環(huán)境復(fù)雜的區(qū)域簇的數(shù)量多，這樣可以相對減小處于復(fù)雜電磁環(huán)境下簇通信被破壞的幾率.

3 拓?fù)渲貥?gòu)算法描述

分簇算法中，節(jié)點有兩種不同角色：一種為簇頭節(jié)點，負(fù)責(zé)整個簇內(nèi)信息的收集和數(shù)據(jù)的處理以及簇間轉(zhuǎn)發(fā)，管理或者控制簇內(nèi)成員節(jié)點；一種為簇內(nèi)普通節(jié)點，負(fù)責(zé)采集其所在監(jiān)測區(qū)域內(nèi)的數(shù)據(jù).由于簇內(nèi)普通節(jié)點與簇頭節(jié)點所承擔(dān)任務(wù)不同，其通信中斷后對網(wǎng)絡(luò)通訊造成的影響如下：

3.1 簇內(nèi)普通節(jié)點的通信受到干擾或者破壞時，節(jié)點通信中斷，會導(dǎo)致其監(jiān)測區(qū)域內(nèi)的數(shù)據(jù)不能被實時采集.干擾消失后，通信重新恢復(fù)繼續(xù)監(jiān)測；若此節(jié)點的通信永久中斷，則可人工或者機械重新布撒新的節(jié)點.可見，此類節(jié)點的通信中斷對其所在的簇或者整個網(wǎng)絡(luò)的影響是非常小的.

3.2 當(dāng)簇頭節(jié)點的通信中斷時，由于簇頭節(jié)點所承擔(dān)網(wǎng)絡(luò)通信任務(wù)的特殊性，將會導(dǎo)致整個簇內(nèi)的數(shù)據(jù)無法得到實時的處理和轉(zhuǎn)發(fā)，而且會導(dǎo)致鏈路中需要經(jīng)過此簇頭進行數(shù)據(jù)轉(zhuǎn)發(fā)的簇的數(shù)據(jù)無法得到及時的轉(zhuǎn)發(fā).此情況對于整個網(wǎng)絡(luò)的數(shù)據(jù)傳輸都有著很大的影響.

因此，簇頭節(jié)點通信中斷后，如何重新快速建立鏈路是本文算法的核心內(nèi)容.

具體算法如下：

（1）簇頭節(jié)點對簇內(nèi)數(shù)據(jù)進行處理，向基站進行轉(zhuǎn)發(fā)，在簇頭向基站發(fā)送的數(shù)據(jù)包中加上一個信息位ngrid，即其所在網(wǎng)格的編號，此數(shù)值唯一且不變.

（2）簇內(nèi)成員節(jié)點將采集到的數(shù)據(jù)向簇頭發(fā)送，在此數(shù)據(jù)包上增加一個信息位SBCL（standbyclusterhead），該信息位數(shù)值為0或1.數(shù)值為1時，表示為節(jié)點為當(dāng)前備用簇頭節(jié)點；數(shù)值為0時，表示節(jié)點不是當(dāng)前備用簇頭節(jié)點.

（3）備用簇頭節(jié)點的選擇主要依據(jù)首選和備選兩個參數(shù).首選參數(shù)是節(jié)點是否在當(dāng)前簇頭所在鏈路中上下跳節(jié)點的通信范圍內(nèi)，若在此通信范圍內(nèi)則作為備用節(jié)點之一，首選參數(shù)即是SBCL數(shù)值；備選參數(shù)是節(jié)點當(dāng)前剩余的能量，當(dāng)滿足主參數(shù)時，擁有剩余能量多的節(jié)點優(yōu)先當(dāng)選.由于本算法的首要目的是快速重構(gòu)鏈路，因此在滿足快速的前提下，再考慮節(jié)點的能耗問題.

判斷節(jié)點是否能成為備用簇頭節(jié)點的判決式為：

Drr判決式中α的數(shù)值由式3-2、3-3決定.

節(jié)點位置信息表示為(xij,yij)，根據(jù)主參數(shù)首先判斷節(jié)點是否在其所在簇上下跳簇頭節(jié)點的通信范圍內(nèi)：

其中，(xi2j2-yi2j2)表示為當(dāng)前可能成為新簇頭節(jié)點的位置坐標(biāo)，(xi1j1,yi1j1)表示為上一跳簇頭節(jié)點的位置坐標(biāo)，(xi3j3,yi3j3)表示為下一跳簇頭節(jié)點的位置坐標(biāo)，i1≠i2≠i3且j1≠j2≠j3

當(dāng)式3-2、3-3同時成立時，α=1；否則α=0；

節(jié)點的drr最大時，該節(jié)點擔(dān)任備用簇頭節(jié)點.

在選舉備用簇頭的判決式中，根據(jù)通信半徑范圍的選舉備用簇頭時會出現(xiàn)三種情況：

第一種情況：簇內(nèi)成員節(jié)點中有滿足α=1的節(jié)點，則在這些節(jié)點中根據(jù)判決式3-1選出能量最高的節(jié)點作為備用節(jié)點.

第二種情況：簇內(nèi)成員節(jié)點中沒有能滿足α=1的節(jié)點，即如果所有的節(jié)點α=0，此時根據(jù)式3-3為此簇選擇能夠直接與上一跳簇頭節(jié)點通信的備用簇頭.當(dāng)式3-3成立時，γ=1；否則γ=0.

此情況下，在滿足γ=1的簇內(nèi)成員節(jié)點中選擇能量最高的節(jié)點作為備用簇頭節(jié)點.

下一跳簇頭由于上一跳簇頭的失效而失去了可以轉(zhuǎn)發(fā)數(shù)據(jù)的鏈路，此時，為下一跳的簇頭選擇新的備用鏈路來完成其數(shù)據(jù)的實時轉(zhuǎn)發(fā).具體方法是：當(dāng)為當(dāng)前簇頭選擇出備用簇頭之后，通知下一跳簇頭選擇備用鏈路，下一跳簇頭在一跳范圍內(nèi)尋找一個最近的簇頭當(dāng)做其備用的轉(zhuǎn)發(fā)簇頭.

第三種情況：所有簇內(nèi)成員節(jié)點無法滿足式3-3時，即節(jié)點的γ=0，則此簇內(nèi)重新按照初始拓?fù)浣r競選簇頭的法則選擇備用簇頭，并在一跳范圍內(nèi)為自己選擇備用鏈路.與第二種情況相同，并通知下一跳簇頭選擇備用鏈路.

（4）簇頭節(jié)點在固定的時隙間都會向基站發(fā)送一條含有其網(wǎng)格信息的數(shù)據(jù)包，若基站在某一時隙沒有收到該網(wǎng)格簇頭節(jié)點發(fā)送來的數(shù)據(jù)包，則判斷該簇頭節(jié)點通信中斷，即刻發(fā)送數(shù)據(jù)包通知該網(wǎng)格中備用的簇頭節(jié)點擔(dān)任簇頭.

（5）若備用簇頭節(jié)點或者選擇的備用鏈路的簇頭節(jié)點也失效，則重新選擇簇頭，并搭建鏈路.

4 仿真場景設(shè)計

為了簡化仿真模型，將仿真場景中電磁情況按照復(fù)雜度分為三個等級：

（1）電磁環(huán)境最簡單（即對無線通信干擾破壞最小）的為Ⅰ級，假設(shè)在此環(huán)境下節(jié)點通信遭到干擾或者破壞的概率為：PⅠ

（2）電磁環(huán)境較復(fù)雜（即對無線通信干擾破壞程度較大）的為Ⅱ級，假設(shè)在此環(huán)境下節(jié)點通信遭到干擾或者破壞的概率為：PⅡ

（3）電磁環(huán)境最復(fù)雜（即對無線通信干擾破壞最大）的為Ⅲ級，假設(shè)在此環(huán)境下節(jié)點通信遭到干擾或者破壞的概率為：PⅢ

在已有的分簇算法中，對網(wǎng)絡(luò)初始拓?fù)涞脑O(shè)計一般有：mesh型，即每個CH到BS為一跳，如LEACH算法；最短路徑樹，如Dijkstra算法[44]；多跳鏈路，如DAEA算法等.

本文設(shè)計一種局部樹狀的多跳鏈路，具體定義如下：鏈路中簇頭與簇頭之間距離為一跳；每個簇頭只與離其最近的兩個簇頭相連作為上一跳簇頭節(jié)點和下一跳簇頭節(jié)點；當(dāng)簇頭節(jié)點是位于電磁環(huán)境為Ⅲ級時，此簇頭節(jié)點作為其所在鏈路的終端簇頭節(jié)點，在此簇頭周圍若存在位于同等級環(huán)境的簇頭節(jié)點亦可以申請加入其上一跳簇頭，即局部樹狀拓?fù)浣Y(jié)構(gòu)產(chǎn)生，如圖4-1所示.

圖4-1 局部樹狀多跳鏈路示意圖

假設(shè)鏈路的跳數(shù)限制為10跳，通過仿真計算，本文設(shè)計的拓?fù)浣Y(jié)構(gòu)在復(fù)雜電磁環(huán)境中通信中斷的概率較小，更適用于此環(huán)境下無線傳感器網(wǎng)絡(luò)的應(yīng)用.

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

MATLAB仿真軟件模擬TCUVG算法中的網(wǎng)絡(luò)環(huán)境，在仿真實驗中布置了1000*1000的網(wǎng)絡(luò)環(huán)境，用非均勻虛擬網(wǎng)格對整個網(wǎng)絡(luò)進行劃分，以區(qū)別監(jiān)測區(qū)域電磁環(huán)境的不同，再隨機布撒N個節(jié)點，節(jié)點一旦布撒則不再移動.如圖5-1所示.

圖5-1 節(jié)點數(shù)為1000的網(wǎng)絡(luò)初始拓樸

表5-1是對節(jié)點數(shù)分別為：1500、2000、2500、3000時，整個網(wǎng)絡(luò)中能夠找到備用簇頭的網(wǎng)格的概率，式5-1：

其中，nsbch為選舉的備用簇頭的數(shù)量，ngrid為整個網(wǎng)絡(luò)中網(wǎng)格數(shù)

表5-1 網(wǎng)絡(luò)中備用簇頭概率

通過表5-1可以看出，網(wǎng)絡(luò)中備用簇頭的選舉概率隨著網(wǎng)絡(luò)的節(jié)點數(shù)的增大而增大，當(dāng)網(wǎng)絡(luò)規(guī)模一定時，節(jié)點數(shù)的增大表示節(jié)點的密度增大，此時根據(jù)式3-1選擇到的備用簇頭的概率也會增大.這樣選擇的備用簇頭可以滿足快速拓?fù)渲貥?gòu)的條件，大大降低用于重新選舉簇頭節(jié)點和重新構(gòu)建鏈路的時間.

網(wǎng)絡(luò)中節(jié)點由于其所處的電磁環(huán)境不同，按照復(fù)雜電磁環(huán)境場景設(shè)計中對節(jié)點失效后通信中斷的概率設(shè)計，并對簇頭節(jié)點通信中斷后，網(wǎng)絡(luò)重新構(gòu)建拓?fù)?，恢?fù)通信所需的時間計算，對網(wǎng)絡(luò)的拓?fù)渲貥?gòu)時間進行計算，結(jié)果如圖5-2、5-3所示.

圖5-2是TCUVG協(xié)議在節(jié)點為1500至3500之間的簇頭平均重構(gòu)時間，當(dāng)節(jié)點數(shù)在1500-3500之間時，TCUVG協(xié)議是傳統(tǒng)重構(gòu)協(xié)議所用死亡時間的50%-63%，可以看出，TCUVG協(xié)議大大提高了用于拓?fù)渲貥?gòu)的時間.

本文定義：當(dāng)網(wǎng)絡(luò)中50%的節(jié)點死忙時，則整個網(wǎng)絡(luò)死亡.在網(wǎng)絡(luò)死亡前，整個網(wǎng)絡(luò)中簇頭節(jié)點用于拓?fù)渲貥?gòu)的時間的統(tǒng)計，如圖5-3.

圖5-2 簇頭節(jié)點平均拓?fù)渲貥?gòu)時間

圖5-3 網(wǎng)絡(luò)死亡時簇頭節(jié)點用于拓?fù)渲貥?gòu)的時間

由于本算法中，提前對網(wǎng)絡(luò)進行固定的分簇并且選舉備用簇頭，使得網(wǎng)絡(luò)中簇頭節(jié)點通信中斷后不用再耗費時間用于分簇和簇頭選舉，備用簇頭可以直接用于網(wǎng)絡(luò)通信，此方法大大降低了網(wǎng)絡(luò)用于拓?fù)渲貥?gòu)的時間，仿真結(jié)果圖也證明了這點.圖5-2中，當(dāng)節(jié)點密度高比節(jié)點密度低的網(wǎng)絡(luò)重構(gòu)時間增加是由于：當(dāng)節(jié)點密度高時，簇頭節(jié)點到達(dá)基站的鏈路數(shù)目會增多，這樣簇頭節(jié)點通信失敗后，基站判斷收到數(shù)據(jù)包延時會加大，通知備用簇頭時間會加大，增加了拓?fù)渲貥?gòu)的時間.圖5-3可以看出，當(dāng)節(jié)點密度增大時，整個網(wǎng)絡(luò)的備用簇頭的選擇概率很大，因此，整個網(wǎng)絡(luò)中用于拓?fù)渲貥?gòu)的時間大大降低.

6 結(jié)束語

本文設(shè)計了一種無線傳感器網(wǎng)絡(luò)應(yīng)用在復(fù)雜環(huán)境下旨在快速恢復(fù)鏈路通信的基于非均勻虛擬網(wǎng)絡(luò)的拓?fù)淇刂扑惴?，并對算法進行了仿真分析，結(jié)果表明，與傳統(tǒng)算法相比，本文設(shè)計的TCUVG算法在大規(guī)模無線傳感器網(wǎng)絡(luò)應(yīng)用中拓?fù)渲貥?gòu)時間大大降低.

〔1〕Akyildiz I F, Weilian S, Sankarasubramaniam Y, et al.A Survey on Sensor Networks [C].IEEE Communications Magazine,2002,40(8):102-11.

〔2〕Tilak S, Abu-Ghazaleh NB, Heinzelman W.A Taxonomy of Wireless Micro-sensor Network Models [C].Mobile Computing and Communications Review, 2002, 1(2):1-8.

〔3〕http://en.wikipedia.org/wiki/Network_topology[OL].

〔4〕石文玉,高飛.復(fù)雜電磁環(huán)境對跨境民族影響研究[J].云南民族大學(xué)學(xué)報：自然科學(xué)版，2012,21（S1）：36-38.

TP393

A

1673-260X（2014）03-0020-03

物聯(lián)網(wǎng)下的IPv4-IPv6過渡技術(shù)的研究(2011zr011)；省級質(zhì)量工程項目“IT服務(wù)外包應(yīng)用型人才培養(yǎng)模式創(chuàng)新實驗區(qū)”[教高〔2009〕9號]；IT服務(wù)外包示范實驗實訓(xùn)中心(2011sysxx01)；省級質(zhì)量工程項目“IT服務(wù)外包示范實習(xí)實訓(xùn)中心”（皖教秘高〔2011〕66號）；安徽新華學(xué)院校級重點學(xué)科建設(shè)資金項目(zdfcx201101)