聶云峰，舒 堅(jiān)，龔佳杰，諶業(yè)斌

(南昌航空大學(xué)信息工程學(xué)院，南昌 330063)

覆蓋問題是無線傳感器網(wǎng)絡(luò)研究領(lǐng)域的基本問題，是衡量無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的重要評價(jià)因子［1－2］。覆蓋問題包含兩個(gè)核心內(nèi)容，即通信覆蓋和感知覆蓋［2－4］，其中通信覆蓋直接影響網(wǎng)絡(luò)連通性，是網(wǎng)絡(luò)正常工作的基礎(chǔ)。通信覆蓋指節(jié)點(diǎn)的信號發(fā)送能力所能到達(dá)的有效空間范圍。相關(guān)研究表明，通信覆蓋問題會產(chǎn)生覆蓋盲區(qū)［2－6］，導(dǎo)致通信質(zhì)量下降和大量數(shù)據(jù)包丟失，嚴(yán)重時(shí)甚至出現(xiàn)網(wǎng)絡(luò)分割問題［5－10］。在無線傳感器網(wǎng)絡(luò)從理論研究走向大規(guī)模應(yīng)用的新形勢下，加強(qiáng)無線傳感器網(wǎng)絡(luò)通信覆蓋研究對無線傳感器網(wǎng)絡(luò)規(guī)劃、診斷和維護(hù)具有重要意義。

為了簡化網(wǎng)絡(luò)覆蓋問題，現(xiàn)有研究通常采用理想圓形發(fā)射模型［8－10］作為節(jié)點(diǎn)覆蓋模型，忽視無線信號在傳播過程中受地形、植被及障礙物影響而產(chǎn)生的信號衰減現(xiàn)象。理想圓盤模型過于簡單且與實(shí)際情況相差很大，導(dǎo)致部分覆蓋控制算法在實(shí)際應(yīng)用中出現(xiàn)失效。大量研究［11－14］表明傳感器節(jié)點(diǎn)的通信覆蓋范圍是不規(guī)則的。文獻(xiàn)［12］對節(jié)點(diǎn)通信覆蓋的不規(guī)則性進(jìn)行了建模，并運(yùn)用 DOI模型(Degree of Irregularity)對無線信號傳播的不規(guī)則性進(jìn)行定量描述，DOI定義為角度每變化一個(gè)單位時(shí)，信號傳播方向上的最大傳播距離變化。DOI模型雖然揭示出RSSI呈不規(guī)則連續(xù)分布，然而該模型是一個(gè)概率模型，在實(shí)際應(yīng)用中具有較大局限性。文獻(xiàn)［13］對DOI模型進(jìn)行了擴(kuò)展，結(jié)合對大量RSSI實(shí)測數(shù)據(jù)的分析，提出更具操作性的RIM經(jīng)驗(yàn)?zāi)Ｐ?Radio Irregularity Model)，然而RIM需要針對具體應(yīng)用環(huán)境采集大量實(shí)驗(yàn)數(shù)據(jù)進(jìn)行參數(shù)估計(jì)。此外，在移動通信領(lǐng)域，確定基站的無線信號覆蓋范圍，普遍采用信道測量的方式，即通過儀器進(jìn)行具體的信道測量，采集RSSI路測數(shù)據(jù)，然后通過對經(jīng)驗(yàn)?zāi)Ｐ瓦M(jìn)行校正，根據(jù)得到的校正模型計(jì)算無線信號覆蓋范圍，該方法具有精度高的優(yōu)點(diǎn)，然而信道測試工作量很大，不適用于大規(guī)模密集部署的無線傳感器網(wǎng)絡(luò)應(yīng)用。

基于以上分析，本文提出了一種通過鄰居節(jié)點(diǎn)采集的RSSI信息來估計(jì)傳感器節(jié)點(diǎn)通信覆蓋范圍的方法(NRRC)，將鄰居節(jié)點(diǎn)按照空間位置劃分到不同扇區(qū)集合，通過對各扇區(qū)內(nèi)的RSSI采樣值進(jìn)行最小二乘擬合，得出各扇區(qū)內(nèi)的對數(shù)距離路徑損耗模型，根據(jù)損耗模型及給定信號衰減閾值可求得該扇區(qū)對應(yīng)的最大通訊半徑;然后將各扇區(qū)進(jìn)行疊加來估計(jì)節(jié)點(diǎn)通訊覆蓋范圍。

1 無線信道模型

無線信號傳播的不規(guī)則性是無線通信系統(tǒng)不可忽視的現(xiàn)象，其影響因素很多，但大致可以分為設(shè)備和傳輸媒介兩類影響因素。設(shè)備相關(guān)影響因素包括天線類型、發(fā)射功率、天線增益及信噪比閾值等;傳輸媒介相關(guān)因素包括介質(zhì)類型、背景噪聲及環(huán)境相關(guān)的因素如地形、植被及障礙物等?？偟膩砜?，無線信號傳播損耗的不規(guī)則性是由傳輸媒介的各向異性及設(shè)備的異構(gòu)性造成的。無線信道模型包括理論模型及經(jīng)驗(yàn)?zāi)Ｐ?，其中適用于無線傳感器網(wǎng)絡(luò)的模型主要有:自由空間傳播模型、對數(shù)－常態(tài)分布模型、對數(shù)距離路徑損耗模型及哈塔模型等。在實(shí)際應(yīng)用環(huán)境中，由于多徑、繞射及障礙物等因素，一般采用對數(shù)距離路徑損耗模型，節(jié)點(diǎn)收到信號時(shí)的路徑損耗為:

式中:d為發(fā)射節(jié)點(diǎn)與接收節(jié)點(diǎn)之間的距離;d0為參考距離，單位為m，通常取1 m;n為路徑衰減因子，表示路徑損耗隨距離增加而增大的快慢程度，與具體環(huán)境有關(guān);PL(d0)表示參考距離為d0時(shí)的路徑損耗，單位為dB。由式(1)簡化可得路徑損耗模型的一般表達(dá)式:

由(2)式可知，路徑損耗L可表示為一個(gè)僅與T－R距離d有關(guān)的函數(shù)，路徑損耗建模的核心內(nèi)容就是針對特定應(yīng)用環(huán)境及其RSSI采樣數(shù)據(jù)，提供一組更具本地化特征的校準(zhǔn)系數(shù)［K0，K1］。

2 NRRC算法

電池能量是無線傳感器網(wǎng)絡(luò)最為稀缺的資源，節(jié)點(diǎn)通信覆蓋評估算法必須具備較少的通信開銷和較低的實(shí)現(xiàn)復(fù)雜度。為了準(zhǔn)確、低成本獲取節(jié)點(diǎn)通訊覆蓋范圍，本文提出了直接通過鄰居節(jié)點(diǎn)的RSSI采樣值來估計(jì)節(jié)點(diǎn)通訊覆蓋范圍的NRRC算法。NRRC算法基于網(wǎng)絡(luò)節(jié)點(diǎn)均勻部署和節(jié)點(diǎn)位置已知兩個(gè)基本假設(shè)，算法主要分為以下幾個(gè)步驟:

①傳感器節(jié)點(diǎn)將采集到的路徑損耗均值{NodeID，NeighbourID，RSSI_AVR}上報(bào)至 Sink節(jié)點(diǎn)，由Sink節(jié)點(diǎn)轉(zhuǎn)發(fā)至后臺NRRC計(jì)算程序。

②對任意傳感器節(jié)點(diǎn)，將其鄰居節(jié)點(diǎn)按照空間位置關(guān)系映射至以該節(jié)點(diǎn)為圓心的N個(gè)互不重疊的扇區(qū)集合S。任意扇區(qū)可用四元組Si={Seq，Angle，R，Nodes}來表示，其中:Seq表示扇區(qū)編號，初始扇區(qū)從坐標(biāo)橫軸正向開始，按逆時(shí)針編號;Angle表示扇區(qū)的角度;R表示扇區(qū)半徑;Nodes表示扇區(qū)包含的傳感器節(jié)點(diǎn)集合。定義參數(shù)MAX表示扇區(qū)包含的最大節(jié)點(diǎn)數(shù)，由于扇區(qū)數(shù)越多更能精確表達(dá)節(jié)點(diǎn)通信覆蓋的不規(guī)則程度，這里取MAX=4。扇區(qū)集合的構(gòu)造滿足以下基本約束條件:

③對任意扇區(qū)Si內(nèi)的RSSI采樣值進(jìn)行最小二乘擬合，可得出扇區(qū)Si相應(yīng)的對數(shù)距離路徑損耗模型。記扇區(qū)Si的RSSI采樣數(shù)據(jù)為M組，某鄰居節(jié)點(diǎn)采樣的實(shí)際路徑損耗記為Lk，由式(2)計(jì)算所得的預(yù)測路徑損耗為。由于測量誤差的存在，Lk與必定存在一定差值，根據(jù)最小二乘理論，使得誤差平方和最小，即:

將式(4)對K0，K1求偏導(dǎo)，令偏導(dǎo)數(shù)等于0可得:

對式(5)簡化，可得:

對式(6)進(jìn)行求解即可獲取修正后的參數(shù)［K0，K1］，進(jìn)而得到經(jīng)本地化校準(zhǔn)的信號損耗模型L=K0+K1lgd。

④對任意扇區(qū)Si，若給定信號衰減閾值MAX_LOST，根據(jù)下式可求得該扇區(qū)對應(yīng)的最大通訊半徑R:

⑤最后，根據(jù)各扇區(qū)的角度及求得的最大通信半徑可得出各扇區(qū)的通信覆蓋范圍，將所有扇區(qū)進(jìn)行疊加其并集即為節(jié)點(diǎn)的通訊覆蓋范圍。

3 實(shí)驗(yàn)分析

為驗(yàn)證所提出算法的有效性，進(jìn)行了實(shí)際傳感器節(jié)點(diǎn)實(shí)驗(yàn)。實(shí)驗(yàn)場地選擇在空曠的足球場;傳感器節(jié)點(diǎn)采用CrossBow公司的Telosb節(jié)點(diǎn);無線收發(fā)芯片采用CC2420，工作頻率為2.4 GHZ;傳感器節(jié)點(diǎn)放置高度均為0.75 m;發(fā)射節(jié)點(diǎn)功率設(shè)置為7(－15 dBm)，每100 ms發(fā)送一個(gè)數(shù)據(jù)包，每個(gè)測試周期連續(xù)發(fā)送200個(gè)數(shù)據(jù)包;設(shè)置路徑損耗閾值MAX_LOST=95 dB。

實(shí)驗(yàn)分為兩個(gè)部分進(jìn)行。實(shí)驗(yàn)一目的在于精確測定傳感器節(jié)點(diǎn)在給定最大路徑損耗閾值95 dB時(shí)的通信覆蓋范圍，為NRRC算法的預(yù)測結(jié)果進(jìn)行驗(yàn)證，其實(shí)驗(yàn)步驟為:固定0號節(jié)點(diǎn)為數(shù)據(jù)發(fā)送節(jié)點(diǎn)，1號節(jié)點(diǎn)為數(shù)據(jù)接收節(jié)點(diǎn);以正北為初始方位，1號節(jié)點(diǎn)以5°為步長，逆時(shí)針繞0號節(jié)點(diǎn)旋轉(zhuǎn)360°;在每旋轉(zhuǎn)一個(gè)步長所對應(yīng)的射線上，記錄1號節(jié)點(diǎn)測得RSSI路徑損耗為95 dB處的距離及當(dāng)前射線角度;將記錄的1號節(jié)點(diǎn)位置用平滑曲線相連，即得0號節(jié)點(diǎn)的實(shí)際通信覆蓋范圍。實(shí)驗(yàn)二的目的是獲取鄰居節(jié)點(diǎn)接收信號時(shí)的RSSI路徑損耗值，為了提高效率，利用10個(gè)數(shù)據(jù)接收節(jié)點(diǎn)，在0號節(jié)點(diǎn)周圍隨機(jī)測試300個(gè)位置并記錄各采樣點(diǎn)的坐標(biāo)及路徑損耗均值。對數(shù)據(jù)進(jìn)行預(yù)處理，首先舍棄路徑損耗大于95 dB的數(shù)據(jù)，得到有效數(shù)據(jù)216個(gè);其次，為簡化計(jì)算，將樣本數(shù)據(jù)的直角坐標(biāo)映射為極坐標(biāo)，并按角度大小進(jìn)行排序;最后對排序后的數(shù)據(jù)，隨機(jī)抽取 12、24、36、48、60、72、84、96、108、120個(gè)樣本數(shù)據(jù)構(gòu)成10組鄰居集合。圖1為節(jié)點(diǎn)鄰居數(shù)量分別為12、48和72時(shí)NRRC算法預(yù)測的覆蓋范圍與實(shí)際覆蓋范圍的對比情況。圖1(a)、圖1(b)及圖1(c)表明鄰居節(jié)點(diǎn)數(shù)越多，NRRC算法預(yù)測的覆蓋范圍與實(shí)際覆蓋范圍越接近，充分說明本文算法的有效性。

定義NRRC預(yù)測范圍為Snrrc，實(shí)際覆蓋范圍為S，則面積誤差E可定義為:

圖1 NRRC算法預(yù)測結(jié)果與實(shí)際信號覆蓋對比

由式(8)計(jì)算上述10組NRRC預(yù)測結(jié)果與實(shí)際覆蓋范圍的面積誤差，如圖2所示。圖2表明:隨著鄰居節(jié)點(diǎn)數(shù)目的增加，面積誤差率呈逐漸減少趨勢;鄰居節(jié)點(diǎn)數(shù)在12～48區(qū)間，面積誤差率呈迅速減少趨勢;鄰居節(jié)點(diǎn)數(shù)在48～72區(qū)間，面積誤差率呈較快減少趨勢;鄰居節(jié)點(diǎn)數(shù)在72～120間面積誤差率呈緩慢減少趨勢;鄰居節(jié)點(diǎn)數(shù)為12時(shí)，面積誤差率最大，高達(dá)26.6%，說明NRRC算法對鄰居節(jié)點(diǎn)的數(shù)量較為敏感，節(jié)點(diǎn)數(shù)越少，預(yù)測誤差越大;鄰居節(jié)點(diǎn)數(shù)約為60～72時(shí)，面積誤差率已小于10%，說明NRRC算法具有理想的預(yù)測效果;鄰居節(jié)點(diǎn)數(shù)為120時(shí)，面積誤差率最小，僅為6.8%，此時(shí)由于鄰居節(jié)點(diǎn)數(shù)足夠多，預(yù)測范圍已十分逼近實(shí)際覆蓋范圍，然而由于無線信號傳播的復(fù)雜性，NRRC算法并不能完全準(zhǔn)確預(yù)測出節(jié)點(diǎn)的實(shí)際通信范圍。

圖2 NRRC算法預(yù)測結(jié)果誤差

4 結(jié)論

無線信號傳播的不規(guī)則性是無線通信系統(tǒng)不可忽視的現(xiàn)象。DOI模型和RIM模型對無線信號傳播的不規(guī)則度進(jìn)行了定量描述，揭示出RSSI路徑損耗呈不規(guī)則連續(xù)分布，然而該類模型需針對具體應(yīng)用環(huán)境采集大量實(shí)驗(yàn)數(shù)據(jù)進(jìn)行模型校正，因此在實(shí)際應(yīng)用中具有較大局限性。本文算法直接通過鄰居節(jié)點(diǎn)采集的RSSI路徑損耗來估計(jì)傳感器節(jié)點(diǎn)通信覆蓋范圍，將鄰居節(jié)點(diǎn)按照空間位置劃分到不同扇區(qū)集合，通過對各扇區(qū)內(nèi)的RSSI采樣值進(jìn)行最小二乘擬合，得出各扇區(qū)內(nèi)的對數(shù)距離路徑損耗模型，根據(jù)損耗模型及給定信號衰減閾值可求得該扇區(qū)對應(yīng)的最大通訊半徑，通過將各扇區(qū)進(jìn)行疊加來估計(jì)節(jié)點(diǎn)通訊覆蓋范圍。實(shí)驗(yàn)結(jié)果表明該方法實(shí)現(xiàn)簡單，不需要進(jìn)行具體實(shí)驗(yàn)，在保證一定鄰居節(jié)點(diǎn)數(shù)量的情況下，能夠充分逼近節(jié)點(diǎn)實(shí)際通信覆蓋范圍，有效提高了節(jié)點(diǎn)通信覆蓋的預(yù)測精度。

本文算法針對密集部署的無線傳感器網(wǎng)絡(luò)應(yīng)用，具有較好的預(yù)測效果，其預(yù)測結(jié)果對無線傳感器網(wǎng)絡(luò)的診斷和維護(hù)具有較大應(yīng)用價(jià)值;對于節(jié)點(diǎn)稀疏部署的應(yīng)用，如何提高算法的預(yù)測精度，有待進(jìn)一步研究。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks:A survey［J］.Computer Networks，2002，38(4):393－422.

［2］Meguerdichian S，Koushanfar F，Potkonjak M，et al.Coverage Problems in Wireless Ad-Hoc Sensor Networks［C］//IEEE Infocom，A-pril 2001，3:1380－1387.

［3］Abrams Z，Goel A，Plotkin S.Set k-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks［C］//Proc.of the 3rd Int’l Conf.on Information Processing in Sensor Networks.Berkeley:ACM Press，2004:424－432.

［4］Carbunar B，Grama A，Vitek J，et al.Coverage Preserving Redundancy Elimination in Sensor Networks［C］//Proc.of the 1st IEEE Conf.on Sensor and Ad Hoc Communications and Networks，Santa Clara:IEEE Press，2004:377－386.

［5］劉明，曹建農(nóng)，鄭源，等.無線傳感器網(wǎng)絡(luò)多重覆蓋問題分析［J］.軟件學(xué)報(bào)，2007，18(1):127－136.

［6］毛鶯池，馮國富，陳力軍，等.與位置無關(guān)的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議［J］.軟件學(xué)報(bào)，2007，18(7):1672－1684.

［7］屈玉貴，藺智挺，趙保華.無線傳感器網(wǎng)絡(luò)的WPCS覆蓋策略［J］.電子與信息學(xué)報(bào)，2007，23(2):486－493.

［8］蔣杰，方力，張鶴穎，等.無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法［J］.軟件學(xué)報(bào)，2006，17(2):175－184.

［9］崔莉，鞠海玲，苗勇，等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2005，42(1):163－174.

［10］劉麗萍，王智，孫優(yōu)賢.無線傳感器網(wǎng)絡(luò)部署及其覆蓋問題研究［J］.電子與信息學(xué)報(bào)，2006，28(9):1752－1777.

［11］方震，趙湛，郭鵬，等.基于RSSI測距分析［J］.傳感技術(shù)學(xué)報(bào)，2007，20(11):2526－2530.

［12］Wu C H，Chung Y C.Heterogeneous Wireless Sensor Network Deployment and Topology Control Based on Irregular Sensor Model［C］//Second International Conference，GPC2007，Paris:IEEE Press，2007:78－88.

［13］Zhou G，He T，Krishnamurthy S，et al.Models and Solutions for Radio Irregularity in Wireless Sensor Networks［J］.ACM Trans.Sen.Netw.，2006，2(2):221－262.

［14］He T，Huang C，Blum B M，et al.Range-Free Localization Schemes for Large Scale Sensor Networks［C］//Proceedings of the 9th AnnualInternational Conference on Mobile Computing and Networking(MobiCom)，San Diego:IEEE Press，2003:81－95.