基于智能化小區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制算法

穆泉伶

摘 要： 無線智能小區(qū)中網(wǎng)絡(luò)節(jié)點的有效能量覆蓋控制是搭建智能化無線網(wǎng)絡(luò)平臺的核心問題。依托當(dāng)前小區(qū)網(wǎng)絡(luò)技術(shù)實際應(yīng)用需求，對不同覆蓋形式的典型算法進行分類描述。提出一種節(jié)點覆蓋重疊最大有效覆蓋率（OMEC）的控制覆蓋算法，有效解決節(jié)點冗余、真空覆蓋等問題。通過仿真實驗?zāi)M對比多種算法，結(jié)果表明該算法在提高網(wǎng)絡(luò)覆蓋質(zhì)量以及延長網(wǎng)絡(luò)服役周期等方面均有較明顯的優(yōu)勢。

關(guān)鍵詞： 智能化小區(qū)； 無線傳感器網(wǎng)絡(luò)； 覆蓋控制； 重疊最大有效覆蓋率

中圖分類號： TN711?34 文獻標(biāo)識碼： A 文章編號： 1004?373X（2017）09?0073?05

Abstract： The network nodes′ effective energy coverage control in wireless intelligent community is the core issue to build the intelligent wireless network platform. On the basis of the actual application requirements of the current community network technology， the typical algorithms with different coverage forms are classified and described. A control coverage algorithm based on overlay maximum effective coverage （OMEC） of node coverage is proposed to solve the problems of node redundancy and vacuum coverage. Multiple algorithms are compared with simulation experiments. The simulation results show that the proposed algorithm has obvious advantages in improvement of the quality of network coverage quality and extension of the network service cycle.

Keywords： intelligent community； wireless sensor network； coverage control； overlay maximum effective coverage

0 引 言

隨著城市數(shù)字化建設(shè)進程的不斷深入，城市小區(qū)智能化建設(shè)水平是城市智慧的最直接體現(xiàn)，其智能化程度直接決定了城市的智慧等級。采用無線傳感技術(shù)搭建小區(qū)無線網(wǎng)絡(luò)平臺實現(xiàn)小區(qū)智能化管理，解決了有線網(wǎng)絡(luò)布線嚴(yán)重浪費、受雷電干擾嚴(yán)重、信號損失過大等弊端。利用體積較小的無線傳感器，以分配節(jié)點的形式組織搭建小區(qū)覆蓋監(jiān)測網(wǎng)絡(luò)。被監(jiān)測到的數(shù)據(jù)由傳輸鏈路通過節(jié)點發(fā)送到基站或者匯集節(jié)點，再傳輸?shù)较到y(tǒng)數(shù)據(jù)網(wǎng)絡(luò)管理平臺。平臺將對數(shù)據(jù)進行感知、采集、分類、分析比對等操作完成基于普通用戶和應(yīng)用程序的訪問及操作。

網(wǎng)絡(luò)覆蓋性和傳輸連通性作為與智能化小區(qū)無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）關(guān)系密切并且核心的問題，其直接影響了網(wǎng)絡(luò)節(jié)點的覆蓋區(qū)域以及覆蓋質(zhì)量，決定了網(wǎng)絡(luò)的生存周期。對于容量較大、配套設(shè)施完善的小區(qū)，無線傳感器節(jié)點的密度必然要與之相匹配，節(jié)點數(shù)量不僅多而且密度大。導(dǎo)致網(wǎng)絡(luò)冗余信息量大，堵塞通信鏈路，網(wǎng)絡(luò)傳輸質(zhì)量低下，網(wǎng)絡(luò)擴展性能降低，網(wǎng)絡(luò)服役周期縮短。另外，從傳感器節(jié)點的角度，節(jié)點向匯聚節(jié)點提供的數(shù)據(jù)正確率降低，導(dǎo)致匯聚節(jié)點進行數(shù)據(jù)收集存在不確定性，與真實數(shù)據(jù)存在較大出入。覆蓋控制決定了智能網(wǎng)絡(luò)是否能夠?qū)崿F(xiàn)有效監(jiān)控能力[1]節(jié)能方面的冗余控制，同時也是解決通信沖突以及過量信息冗余的另一個需要著重解決的問題[2]。

1 WSN中覆蓋控制算法類別

1.1 NSS算法[3]

NSS（Node Self?Scheduling）算法可以歸結(jié)為確定性覆蓋中的區(qū)域覆蓋以及節(jié)能覆蓋范疇。算法的優(yōu)勢明顯：較好地解決了“覆蓋遺失”的問題，實現(xiàn)了網(wǎng)絡(luò)范圍的完全覆蓋。在正常工作狀態(tài)下，傳感器節(jié)點可以區(qū)分為Sleep（睡眠）和Active（活躍）兩種典型的狀態(tài)。算法使得節(jié)點在兩種狀態(tài)下輪流工作，整個工作周期通過節(jié)點狀態(tài)轉(zhuǎn)換和工作兩個階段組成。在Active狀態(tài)下，每個節(jié)點第一步要向其有效覆蓋距離之內(nèi)的鄰居節(jié)點發(fā)送包括節(jié)點ID以及所在位置的廣播信息，判斷是否有鄰居節(jié)點可以完成自身的感知任務(wù)。接下來的過程分為兩種情況：若有可以替代的節(jié)點，則替代節(jié)點返回給該節(jié)點一條信息，節(jié)點進入Sleep狀態(tài)；否則，節(jié)點繼續(xù)進行感知。當(dāng)節(jié)點和都處于其鄰居節(jié)點包含的覆蓋范圍之內(nèi)，且和同時符合睡眠條件，這就出現(xiàn)了不能被監(jiān)測的區(qū)域，即網(wǎng)絡(luò)“覆蓋遺失”，如圖1所示。為了解決覆蓋遺失的問題，每個節(jié)點都需要在等待“退避時間”后才能進行狀態(tài)檢驗，當(dāng)節(jié)點符合睡眠狀態(tài)時，還要進一步等待一定時間實時監(jiān)聽鄰居節(jié)點的狀態(tài)。但是，算法也存在一定的缺陷：邊界節(jié)點在節(jié)點狀態(tài)轉(zhuǎn)換過程中不能進入Sleep狀態(tài)，這將導(dǎo)致邊界節(jié)點的生命周期過短，加劇了網(wǎng)絡(luò)能耗。

在無線傳感器網(wǎng)絡(luò)中，節(jié)點能效的高效利用對于網(wǎng)絡(luò)生命周期起著決定性的影響。采用節(jié)點Sleep和Active兩種狀態(tài)相輪換的工作方式，進而達到節(jié)能高效的目的，同時亦可相對有效地延長網(wǎng)絡(luò)生命周期。這就要求在滿足一定網(wǎng)絡(luò)覆蓋率的前提下，最大化的對節(jié)點集進行輪換[4?8]。

1.2 OGDC算法[9]

OGDC（Optimal Geographical Density Control）算法研究在滿足無線傳感器網(wǎng)絡(luò)的覆蓋范圍及保證網(wǎng)絡(luò)通信連通性的前提下，節(jié)點數(shù)量最小化的解決方法。算法將網(wǎng)絡(luò)工作過程劃分為長度相同的時間段，每個時間段開始時，網(wǎng)絡(luò)中節(jié)點都缺省為“監(jiān)聽”節(jié)點，在進行選擇后，若干節(jié)點被確定為工作節(jié)點，根據(jù)激活節(jié)點的兩種不同位置形式確定下一個被激活的節(jié)點。

形式一：對于已知位置的一個激活節(jié)點，其下一個較優(yōu)的激活節(jié)點的位置應(yīng)該大約在距離此激活節(jié)點的覆蓋半徑處；

形式二：對于已知位置的兩個激活節(jié)點在此兩個激活節(jié)點的連線中點處取垂線，以兩個激活節(jié)點為圓心的覆蓋范圍的交點（并和垂線相交）為起始點在垂線上取距離為覆蓋半徑的點處就是第三個激活節(jié)點的較優(yōu)位置。若在較優(yōu)位置沒有所需節(jié)點，則應(yīng)該尋找確定距離較優(yōu)位置最近的節(jié)點作為激活節(jié)點，如圖2所示。

隨機規(guī)避機制可以使得網(wǎng)絡(luò)中節(jié)點均勻耗能，并且能較好地解決信道沖突問題。收到發(fā)布消息的節(jié)點，根據(jù)算法設(shè)定本身狀態(tài)為“工作”或者是“睡眠”，且這一狀態(tài)在整個當(dāng)前時間段內(nèi)保持不變，直到下一個時間段開始。

1.3 PEAS算法[10]

PEAS（Probing Environment and Adaptive Sleeping）算法中的節(jié)點一般處于睡眠、探測和工作三種狀態(tài)。算法優(yōu)勢體現(xiàn)在：無需提前保存和獲知鄰居節(jié)點的位置信息、可以對冗余節(jié)點進行關(guān)閉，所以節(jié)能效果顯著。節(jié)點初始缺省狀態(tài)均為睡眠狀態(tài)，睡眠時間由探測速率確定。節(jié)點蘇醒之后以一定的功率在設(shè)定范圍內(nèi)廣播探測消息。如有工作節(jié)點，則收到消息后返回一則回復(fù)消息，睡眠節(jié)點重新恢復(fù)到睡眠狀態(tài)。若內(nèi)無工作節(jié)點回復(fù)消息，則睡眠節(jié)點開始工作。對于工作節(jié)點，如果在一定時間段之內(nèi)接收不到回復(fù)消息，則工作節(jié)點須一直保持工作狀態(tài)，就會出現(xiàn)負載過量，致使其耗盡能量，提前死亡。

由于篇幅有限，僅選擇以上三種比較常見的算法進行簡要說明，但是目前的網(wǎng)絡(luò)覆蓋控制算法大多還是將研究的重點放在區(qū)域覆蓋的完全性上面。在對工作節(jié)點的選擇工程中存在能耗過大，信息傳輸部分丟失等弊端。在智能化小區(qū)網(wǎng)絡(luò)系統(tǒng)建設(shè)過程中，考慮在滿足實際應(yīng)用需求的前提下，網(wǎng)絡(luò)區(qū)域只要滿足一定的有效覆蓋率即可，并不需要網(wǎng)絡(luò)區(qū)域的完全覆蓋，所以，有必要面向自身需求開發(fā)適合的算法（OMEC），實現(xiàn)節(jié)能、高效、穩(wěn)定、安全的應(yīng)用目標(biāo)。

2 針對最大有效覆蓋率的節(jié)點控制覆蓋算法

本文設(shè)計提出了針對節(jié)點覆蓋重疊最大有效覆蓋率的控制覆蓋算法OMEC（Overlay Maximum Effective Coverage），結(jié)合智能小區(qū)的實際構(gòu)建環(huán)境，能有效提高網(wǎng)絡(luò)覆蓋標(biāo)準(zhǔn)，保證信息傳輸準(zhǔn)確，解決數(shù)據(jù)包的沖突問題，減少網(wǎng)絡(luò)消耗，延長網(wǎng)絡(luò)生存周期。

為了使討論的問題具有普遍性，所有無線傳感器節(jié)點均放置在指定邊長的二維方形區(qū)域內(nèi)?，F(xiàn)假定網(wǎng)絡(luò)環(huán)境為如下形式：每個節(jié)點的網(wǎng)絡(luò)覆蓋距離均遠小于所設(shè)置的實際網(wǎng)絡(luò)區(qū)域范圍；所有節(jié)點在網(wǎng)絡(luò)中地位相同，各節(jié)點之間互相獨立；當(dāng)所有節(jié)點均為工作狀態(tài)時，節(jié)點覆蓋區(qū)域可以滿足實際設(shè)置網(wǎng)絡(luò)的要求。即體現(xiàn)節(jié)點高密度、大規(guī)模的網(wǎng)絡(luò)部署特點；具有網(wǎng)絡(luò)中節(jié)點同構(gòu)，即每個節(jié)點具有相等的感知半徑和通信半徑，且需要滿足通信間距必須≥2倍感知間距；網(wǎng)絡(luò)中所有節(jié)點都要保持時鐘同步。

2.1 最大覆蓋面積和有效覆蓋面積率

2.2.2 冗余節(jié)點的冗余覆蓋度

定理2 個隸屬于某一個傳感器節(jié)點的冗余節(jié)點的冗余覆蓋度是（當(dāng)傳感器節(jié)點和它的鄰居節(jié)點互相作為冗余節(jié)點時，傳感器節(jié)點同它的鄰居節(jié)點的感知面積比值叫做冗余覆蓋度）：

算法在應(yīng)用概率原理、通信鏈路原理等基礎(chǔ)理論指導(dǎo)下尋求網(wǎng)絡(luò)無線傳感器的最大有效覆蓋面積和較低的冗余覆蓋率。結(jié)合節(jié)點建立冗余連通圖，通過設(shè)定閾值判定節(jié)點的冗余度是否低于閾值標(biāo)準(zhǔn)。通過節(jié)點信息，在鏈表中按照高低保存節(jié)點能量，達到節(jié)省網(wǎng)絡(luò)開銷，降低能耗的目的。

3 仿真實驗比對分析

為了驗證本文提出算法的可行性和穩(wěn)定性，應(yīng)用C語言開發(fā)了一個仿真平臺，以100 m×100 m為實驗覆蓋區(qū)域范圍，對本文OMEC算法和文中提到的文獻算法在不同類型節(jié)點數(shù)量、網(wǎng)絡(luò)傳輸覆蓋率、冗余節(jié)點數(shù)量以及算法的網(wǎng)絡(luò)生命周期等方面做了仿真實驗對比，實驗結(jié)果較好地驗證了本文算法的可靠性，具有較明顯的優(yōu)勢。

仿真結(jié)果如圖5～圖8所示。圖5顯示， OMEC算法在參數(shù)作用下對應(yīng)相同的傳感器節(jié)點，需要的工作節(jié)點數(shù)量明顯少于其他算法。因為NSS與PEAS算法皆是通過加大傳感器節(jié)點數(shù)量的方式達到對被監(jiān)測區(qū)域的最大有效覆蓋。圖6顯示，網(wǎng)絡(luò)覆蓋率與傳感器節(jié)點的數(shù)量成正比。OMEC算法通過參數(shù)有效動態(tài)調(diào)節(jié)被檢測區(qū)域的覆蓋率，所以在初期階段的覆蓋率就要高于其他算法。在節(jié)點數(shù)量為108時，OMEC算法實現(xiàn)了最大面積的有效覆蓋，其他算法分別在節(jié)點數(shù)量為129和138時達到有效覆蓋。在有效覆蓋方面，比較OMEC與其他兩種算法的覆蓋率平均值，覆蓋率提升了12.3%。

圖7顯示，所有算法的冗余節(jié)點數(shù)量和網(wǎng)絡(luò)有效覆蓋率皆成反比。圖8中，最初OMEC與NSS算法的網(wǎng)絡(luò)生命周期大致相同，但是隨著傳感器節(jié)點數(shù)量的加大，兩種算法的網(wǎng)絡(luò)生存周期都有了不同程度的延長。在傳感器節(jié)點數(shù)量為90時，網(wǎng)絡(luò)生命周期達到基本平穩(wěn)的狀態(tài)。OMEC與NSS算法相比較，平均網(wǎng)絡(luò)生命周期上升15.6%。相較于NSS非線性連續(xù)不間斷的覆蓋方式監(jiān)測目標(biāo)節(jié)點，OMEC在能耗方面也有明顯優(yōu)勢。

4 結(jié) 論

本文對智能化小區(qū)的無線傳感器網(wǎng)絡(luò)覆蓋控制算法進行了深入、系統(tǒng)的研究。算法在滿足最大有效覆蓋率的前提下對節(jié)點控制覆蓋進行了求解和驗證，應(yīng)用概率方法對冗余節(jié)點進行判斷。采用模擬仿真平臺對本文算法與文獻算法在節(jié)點數(shù)量、覆蓋率、生存周期對比等方面進行實驗比對及分析，結(jié)果表明，本文提出的算法具有一定的可行性，而且存在較為明顯的優(yōu)勢。

參考文獻

[1] 李明，石為人.異構(gòu)傳感器網(wǎng)絡(luò)成本最優(yōu)節(jié)點部署機制[J].重慶大學(xué)學(xué)報，2012，35（2）：55?59.

[2] 謝潔銳，劉才興，胡月明，等.無線傳感器網(wǎng)絡(luò)的部署[J].傳感器與微系統(tǒng)，2007，26（1）：4?7.

[3] VELTRI G， HUANG Q， QU G， et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks [C]// Proceedings of the ACM International Conference on Embedded Networked Sensor System. New York： ACM， 2003： 40?50.

[4] LI X Y. Coverage in wireless and sensor networks [J]. IEEE transactions on computers， 2003， 52（6）： 753?763.

[5] CARLE J， GALLAIS A， SIMPLOT?RYI D. Preserving area coverage in wireless sensor networks using surface coverage relay dominating sets [C]// Proceedings of 2005 the 10th IEEE symposium on Computers and Communications. Cartagena： IEEE， 2005： 347?352.

[6] CARLE J， SIMPLOT?RYI D. Energy efficient area monitoring by sensor networks [J]. IEEE computer magazine， 2004， 37（2）： 40?46.

[7] ZHANG H H， HOU J C. Maintaining sensing coverage and connectivity in large sensor networks [C]// Proceedings of 2004 NSF International Workshop on Theoretical and Algorithmic Aspect of Sensors， Ad Wireless and Peer?to?Peer Network. [S.l.]： NSF， 2004： 89?124.

[8] TIAN D. A node scheduling scheme for energy conservation in large wireless sensor networks [J]. Wireless communications and mobile computing， 2003， 3（2）： 271?290.

[9] YE F， ZHONG G M， LU S， et al. PEAS： a robust energy conserving protocol for long lived sensor network [C]// Proceedings of the 23rd International Conference on Distributed Computing Systems. Washington， DC.， IEEE， 2003： 28?37.