王　翥，呂翠翠，王　玲

(哈爾濱工業(yè)大學(xué)(威海)信息與電氣工程學(xué)院，山東威?！?64209)

0　引言

無(wú)線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)是多學(xué)科交叉的前沿研究熱點(diǎn)。它是由大量具有特定功能的傳感器節(jié)點(diǎn)通過(guò)自組織的無(wú)線通信方式，相互傳遞信息，協(xié)同完成特定功能的智能專用網(wǎng)絡(luò)[1]，在環(huán)境監(jiān)測(cè)、智能交通、醫(yī)療護(hù)理及工業(yè)自動(dòng)化領(lǐng)域有廣泛的應(yīng)用前景[2]。

WSN由3種類型節(jié)點(diǎn)組成：傳感器節(jié)點(diǎn)SN(Sensor Node)、中繼節(jié)點(diǎn)RN(Relay Node)和Sink節(jié)點(diǎn)。WSN通信能力有限，通信的能量消耗通常與通信距離成指數(shù)關(guān)系，通信距離的增加會(huì)導(dǎo)致無(wú)線通信的能量消耗急劇增加[3]。由于SN的微型化，節(jié)點(diǎn)的電池能量有限，所以能量限制是整個(gè)WSN的瓶頸，它決定著網(wǎng)絡(luò)的壽命。為節(jié)省能量，WSN應(yīng)采用多跳路由的通信傳輸機(jī)制，即SN通過(guò)RN轉(zhuǎn)發(fā)數(shù)據(jù)至sink，盡量減少單跳的通信距離，同時(shí)多跳通信也能克服遠(yuǎn)距離無(wú)線通信所遇到的一些信號(hào)傳播效應(yīng)問(wèn)題。

RN布局是多跳路由的關(guān)鍵，它決定著是否可以減小網(wǎng)絡(luò)能量消耗、延長(zhǎng)網(wǎng)絡(luò)壽命。文獻(xiàn)[4-5]從理論上分析了影響RN布局的因素。文獻(xiàn)[6]通過(guò)近似算法放置RN，使網(wǎng)絡(luò)整體功耗達(dá)到最小。樊勇等提出一種RN多級(jí)擺放策略[7]，全巧艷等用基于正方形網(wǎng)格能量模型的方法均衡網(wǎng)絡(luò)能量消耗[8]。在Lu等的文獻(xiàn)[9]中，基于平衡所有SN和RN的功耗，作者推導(dǎo)出一個(gè)RN密度函數(shù)，根據(jù)密度函數(shù)在感知區(qū)域放置RN.為保證網(wǎng)絡(luò)中放置的RN數(shù)目最少，Satyajayant 等在文獻(xiàn)[10]提出了一種受限的RN布局構(gòu)想，設(shè)定雙向的通信路徑。文獻(xiàn)[11]通過(guò)在WSN中加入冗余的RN增加網(wǎng)絡(luò)的可靠性，保證在WSN的初步設(shè)計(jì)中，每個(gè)SN到基站有k個(gè)節(jié)點(diǎn)不相交的路徑。

上述文獻(xiàn)研究了單約束條件下RN的布局算法，對(duì)于多約束條件下的RN，文中提出一種基于貪婪算法的RN布局方法。傳統(tǒng)基于貪婪算法的路由協(xié)議選擇離sink最近的RN作為下一跳[12]，與傳統(tǒng)貪婪算法不同，文中制定雙重貪婪準(zhǔn)則，根據(jù)最優(yōu)通信距離和多約束條件選擇RN，實(shí)現(xiàn)WSN能量消耗小的目標(biāo)。

1　網(wǎng)絡(luò)模型

用圖G表示一個(gè)WSN，定義如下：

G=(V，E)

式中：V為頂點(diǎn)集；E為圖中邊的集合。

符號(hào)定義如下：

SN集合：S0={s1，s2，…s，s2，…si，…，sn}；Si；標(biāo)號(hào)為i的SN，n：SN的數(shù)目。

RN集合：R0={r1，r2，…，rj，…，rm}；rj：標(biāo)號(hào)為j的RN；m：RN的數(shù)目。

v0：sink節(jié)點(diǎn)，v1…vn：SN，vn+1…vn+m：RN，V={v0，v1，v2，…，vn，vn+1，…vn+m}。

Cvi：節(jié)點(diǎn)vi的通信容量，wvi：vi的流量負(fù)荷(vi轉(zhuǎn)發(fā)的流量)，RCvi：vi冗余流量。

RCvi=Cvi-wvi

節(jié)點(diǎn)的能量消耗分為3部分：感知、通信和數(shù)據(jù)處理。發(fā)送數(shù)據(jù)的消耗為0.38～0.7 W，接收數(shù)據(jù)的能量消耗為0.36 W，感知的能量消耗為0.02 W[13]。在100 m的網(wǎng)絡(luò)上傳輸1KB數(shù)據(jù)與處理3×107條指令消耗的能量大致相等，可見(jiàn)在數(shù)據(jù)通信方面消耗的能量最大。文中主要考慮數(shù)據(jù)通信的能量消耗。

對(duì)于距離為d，長(zhǎng)度為L(zhǎng)bit的信息，發(fā)送所消耗的能量如式(1)所示。

ETx(d，L)=(α1+α2dn1)·L

(1)

接收Lbit的信息所消耗的能量如式(2)所示。

ERx(L)=β·L

(2)

式中：α1、α2和β為參數(shù)；β為路徑損耗指數(shù)；n1∈[2，4]。

SN與RN的角色不同，SN的主要任務(wù)是采集數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行處理，然后發(fā)送數(shù)據(jù)。RN本身不采集數(shù)據(jù)，只轉(zhuǎn)發(fā)SN的數(shù)據(jù)或其它RN的數(shù)據(jù)。

在滿足能量的條件下，vi接收并轉(zhuǎn)發(fā)的數(shù)據(jù)量分別為L(zhǎng)Rx(vi)、LTx(vi)，一般有式(3)。

LTx(vi)=LRx(vi)=L(vi)

(3)

那么消耗的總能量為E(vi)：

E(vi)=ERx〔LRх(vi)〕+ETx〔dih，LTx(vi)〕，(dih≤R)

(4)

傳感器節(jié)點(diǎn)vj發(fā)送的數(shù)據(jù)總量LTx(vj)，因?yàn)樗晦D(zhuǎn)發(fā)RN和其它SN的數(shù)據(jù)，可以忽略接收數(shù)據(jù)時(shí)消耗的能量ERx(LRx(vj))，即：

ERx(LRx(Vj))≈0(J)

(5)

E(vj)=ETx(dj，k，LTx(vj))，(djk≤R)

(6)

由上述公式可知：節(jié)點(diǎn)的能量消耗不僅與通信距離有關(guān)，還與數(shù)據(jù)量(通信容量)有關(guān)。

在多跳路由中，通信距離取決于器件參數(shù)和實(shí)際環(huán)境參數(shù)。節(jié)點(diǎn)之間的最優(yōu)通信距離d0由公式(7)確定[14]。

(7)

源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的距離d通常不是d0的整數(shù)倍，因此最優(yōu)跳數(shù)k是最接近d/d0的整數(shù)。文中對(duì)于任意傳感器節(jié)點(diǎn)vi，當(dāng)di0≥d0時(shí)，采用多跳通信方式；當(dāng)di0

2　貪婪算法

2．1貪婪算法的描述

貪婪算法是一種求最優(yōu)解的簡(jiǎn)單、迅速的設(shè)計(jì)技術(shù)，它采用的是逐步構(gòu)造最優(yōu)解的思想，該算法容易設(shè)計(jì)、實(shí)現(xiàn)并且節(jié)省時(shí)間，它的典型應(yīng)用是最優(yōu)化問(wèn)題。

使用貪婪算法解決RN布局問(wèn)題需要做好3個(gè)方面：

(1)明確求解目標(biāo)；

(2)分析RN布局問(wèn)題所包含的約束條件；

(3)制定貪婪準(zhǔn)則。

RN布局的目標(biāo)函數(shù)用如下數(shù)學(xué)模型表示：

約束條件包括：

(1)SN數(shù)據(jù)轉(zhuǎn)送次數(shù)不超過(guò)規(guī)定的上限值；

(2)通信路徑滿足路徑“不可逆”約束條件；

(3)每個(gè)RN的數(shù)據(jù)轉(zhuǎn)送率不能超過(guò)該節(jié)點(diǎn)所限定的最大數(shù)據(jù)轉(zhuǎn)送率(通信容量)。

規(guī)定s1、s2的數(shù)據(jù)轉(zhuǎn)送次數(shù)上限值為1，如圖1所示。

圖1　數(shù)據(jù)轉(zhuǎn)送次數(shù)示意圖

由圖1可知：s1的數(shù)據(jù)轉(zhuǎn)送次數(shù)為1，滿足條件；s2的數(shù)據(jù)轉(zhuǎn)送次數(shù)為2，超過(guò)1，不滿足條件。

根據(jù)SN到v0的距離d以及d0，規(guī)定數(shù)據(jù)轉(zhuǎn)送次數(shù)上限值。

路徑“不可逆”是指滿足式(7)的通信路徑，如圖2所示。

(7)

式中：1≤i≤n；n+1≤j≤n+m。

圖2　路徑“不可逆”示意圖

由圖2看出：

(8)

(9)

假定SN的數(shù)目、位置以及v0的位置是已知的，設(shè)置SN跳數(shù)為0，RN布局的具體步驟如下。

(1)計(jì)算si(1≤i≤n)與v0之間的距離di0，d={d10，d20，…dn0} 。

(2)當(dāng)di0≤d0時(shí)，si可以與v0直接通信，刪除S0中的si，然后在d中刪除si對(duì)應(yīng)的di0。

(3)當(dāng)di0>d0時(shí)，將di0按降序排列，令nrdi是最接近di0/d0的整數(shù)，如果有多個(gè)相同的最大值(或最小值)，那么它們按SN標(biāo)號(hào)由小及大的順序依次排序。

(4)從具有最大di0值的si開(kāi)始(“最遠(yuǎn)-最近”準(zhǔn)則)，在si與v0的連線上以di0/nrdi為步長(zhǎng)放置RN，令ri1是si的第一跳中繼節(jié)點(diǎn)，RN_one={ri}，刪除S0中的si以及d中對(duì)應(yīng)的di0。

(5)對(duì)于S0中滿足di0>d0的si，計(jì)算它與ri1的距離di(i1)，當(dāng)滿足di(i1)≤d0，假定si是ri1的子節(jié)點(diǎn)。

(6)每個(gè)si產(chǎn)生的數(shù)據(jù)量為dc，每個(gè)RN通信容量為cm，計(jì)算ri1子節(jié)點(diǎn)的個(gè)數(shù)，記為num(ri1)child，令Cri1=cm，wri1=dc·(num(ri1)child+1)，RCr(i1)=Cri1-wri1。

RCr(i1)≥0時(shí)，滿足路徑“不可逆”的si是ri1的子節(jié)點(diǎn)，刪除S0中的si及si對(duì)應(yīng)的di0。

RCr(i1)<0時(shí)，計(jì)算siri1與ri1v0的夾角θ，θ按升序排列，依次從最小θ開(kāi)始(“最小”準(zhǔn)則)，驗(yàn)證θ與是否是銳角，以及ri1是否滿足通信容量要求。

若θ是銳角，并且ri1滿足通信通量要求時(shí)，更新num(ri1child，wri1記為num(ri1)childnew、wri1new。同時(shí)刪除S0中θ對(duì)應(yīng)的si及si對(duì)應(yīng)的di0。

num(ri1)childnew=num(ri1)childnew+1

(10)

RC(ri1=Cri1-wri1new

(11)

重復(fù)驗(yàn)證θ與是否是銳角，以及ri1是否滿足通信容量要求。若同時(shí)滿足條件，那么更新num(ri1childnew、RCr(i1)，直至θ≥90°或RCri1<0時(shí)結(jié)束。

(7)重復(fù)執(zhí)行(4)～ (6)，直至d=φ。

2．2算法的復(fù)雜度

3　實(shí)驗(yàn)結(jié)果分析

在300 m×300 m的監(jiān)測(cè)區(qū)域內(nèi)放置SN和sink，用MatLAB對(duì)上述貪婪算法進(jìn)行仿真，并與其它貪婪算法進(jìn)行比較，通過(guò)網(wǎng)絡(luò)的總能量消耗、RN數(shù)目評(píng)估算法的性能，實(shí)驗(yàn)參數(shù)如表1所示，實(shí)驗(yàn)結(jié)果如圖3～圖5所示。

表1　實(shí)驗(yàn)參數(shù)

其它貪婪算法在WSN應(yīng)用中的貪婪準(zhǔn)則通常為“最近準(zhǔn)則”，即節(jié)點(diǎn)v選擇離sink最近的RN作為下一跳[12]。

圖3中A、B柱狀圖分別表示根據(jù)“最遠(yuǎn)-最近”準(zhǔn)則、“最遠(yuǎn)-最小”準(zhǔn)則時(shí)的WSN總能量消耗情況。圖4中C、D柱狀圖分別表示根據(jù)“最遠(yuǎn)-最近”準(zhǔn)則、“最遠(yuǎn)-最小”準(zhǔn)則時(shí)的SN能量消耗情況。從圖3、圖4可知，傳感器節(jié)點(diǎn)數(shù)目相同時(shí)，由“最遠(yuǎn)-最小”準(zhǔn)則的貪婪算法獲得的SN能量消耗、總能量消耗比一般貪婪算法獲得的能量消耗小。

從圖3看出，WSN總的能量消耗隨SN數(shù)目的增加大致呈增加趨勢(shì)。這與理論能量消耗的趨勢(shì)相符。此外，還可以觀察到：由“最遠(yuǎn)-最小”準(zhǔn)則的貪婪算法得到的總能量消耗較小。圖5中a、b曲線分別表示表示“最遠(yuǎn)-最近”準(zhǔn)則、“最遠(yuǎn)-最小”準(zhǔn)則的RN數(shù)目隨SN數(shù)目的變化，從圖5可知兩曲線的趨勢(shì)大體一致，即RN數(shù)目隨SN數(shù)目的增加而增加。

圖3　WSN的能量消耗

圖4　SN的能量消耗

圖5　RN數(shù)目的比較

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

文中對(duì)WSN中繼節(jié)點(diǎn)布局問(wèn)題進(jìn)行研究，提出傳感器節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)送次數(shù)、數(shù)據(jù)傳輸路徑“不可逆”等約束條件。根據(jù)節(jié)點(diǎn)之間的最優(yōu)通信距離設(shè)置滿足上述條件的“最遠(yuǎn)-最小”貪婪準(zhǔn)則。在傳感器節(jié)點(diǎn)的數(shù)目相同的情況下，與其它貪婪準(zhǔn)則的貪婪算法比較，文中提出的“最遠(yuǎn)-最小”貪婪準(zhǔn)則的貪婪算法WSN整體的能量消耗小。

參考文獻(xiàn)：

[1]AKVIDIZ I F SU W，SANKARASUBRAMANIAM Y，et al．Wireless sensor network：a survey．computer Networks，2002，38：393-341．

[2]陳林星．無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用．北京：電子工業(yè)出版社，2009：1-23．

[3]王殊．無(wú)線傳感器網(wǎng)絡(luò)的理論及應(yīng)用．北京：北京航空航天出版社，2007：2-10．

[4]VALLIMAYIL A，DHULIPALA V R S，RAGHUNATH K M K，et al．Role of relay node in Wireless Sensor Network：A survey．2011 3rd International Conference on Electronics Computer Technology (ICECT)，2011，5：160 -167．

[5]HAN X F，CAO X，ERROL L L，et al．Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks．IEEE Transactions on Mobile Computing，2010，9(5)：643-656．

[6]陸克中，劉剛，陶耀東，等．無(wú)線傳感器網(wǎng)絡(luò)中繼節(jié)點(diǎn)的最小功耗布置算法．小型微型計(jì)算機(jī)系統(tǒng)，2011，32(6)：1035-1040．

[7]樊勇，張曉彤，萬(wàn)亞?wèn)|，等．實(shí)現(xiàn)能量均衡消耗的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)擺放策略．計(jì)算機(jī)工程，2007，33(16)：11-13．

[8]全巧艷，鄧宗白．基于正方形網(wǎng)格能量模型的能量均衡策略．工業(yè)儀表與自動(dòng)化裝置，2010(4)：7-9．

[9]LU K，LIU G，MAO R，et al．Relay node placement based on balancing power consumption in wireless sensor networks．Wireless Sensor Systems，2011，1(1)：1-6．

[10]MISRA S，HONG S D，XUE G L，et．a(chǎn)l．Constrained Relay Node Placement in Wireless Sensor Networks：Formulation and Approximations．IEEE/ACM Transactions on networking，2010，18(2)：434-447．

[11]SITANAYAH L，BROEN K N，SREENAN C J．Fault-Tolerant Relay Deployment for k Node-Disjoint Paths in Wireless Sensor Networks．2011 IFIP Wireless Days，WD 2011，Niagara Falls，2011：1-6．

[12]吳謀，張晴．自適應(yīng)的移動(dòng)Ad hoc網(wǎng)絡(luò)貪婪地理路由協(xié)議．計(jì)算機(jī)應(yīng)用研究，2010，27(8)：3124-3126．

[13]RAGHUNTHAN V，SCHURGERS C，PARK S，et al．Energy-aware wireless microsensor networks．IEEE Signal Processing，2002，19 (6)：40-50．

[14]BHARDWAJ M，GARNETT T，CHANDRAKASAN A P．Upper Bounds on the Lifetime of Sensor Networks．Proc．IEEEICC2001，2001：785-790．