基于人工勢場方法的WSN傳感覆蓋率提高算法*

王 佳

(上海工程技術大學工程實訓中心，上海201620)

近十幾年來對無線傳感器網絡(WSN)的研究方興未艾。簡單地說，WSN就是由一系列小尺寸、多功能的無線傳感節點組成的網絡，各節點合作感知環境、并進行簡單的數據處理和短距離的無線通信[1]。WSN適用于多種工業及商業環境領域，特別是在協作搜索、救援、探測及目標跟蹤等任務中能發揮極大的作用。不同的性能指標評價WSN系統的不同方面，傳感覆蓋率是WSN中重要的性能指標之一，有效的覆蓋策略能夠大大地提高整個WSN系統的工作效率和使用壽命[1]。

傳感覆蓋率的概念是針對WSN中傳感器的傳感效率而提出的，主要用于描述傳感節點對所在物理環境的感知情況[2]，其目的是使待測范圍內的被監測點盡可能多地被節點覆蓋，至少被一個傳感節點覆蓋，并且盡量使所有監測點均被覆蓋。由文獻[3]可知，目前的對覆蓋率的研究主要分成以下幾種方式:區域覆蓋，點覆蓋以及柵欄覆蓋。

對傳感節點進行有效的部署能顯著提高覆蓋率。文獻[3]介紹了隨機部署和提前計劃兩種部署方式。提前計劃主要適用于環境已知的條件下，但是無線傳感網絡常應用在環境未知，人不適宜到達的地方，因此該方法的適用范圍有限。隨機部署適用于自然條件惡劣的環境中，特別是人類不易到達或對人體有害的環境。然而隨機部署可能會出現部分區域節點分布過緊密，而某些區域節點相距太遠的情況，這導致某些區域被多重測量而部分區域則無法被傳感節點覆蓋，導致傳感覆蓋率低。因此，在進行隨機部署之后有必要對各節點位置進行調整以提高整個系統的傳感覆蓋率。文獻[4]利用粒子群優化算法提高傳感覆蓋率。

目前，改善覆蓋百分比主要有以下幾種方法，一種方法是加強節點的傳感和通信范圍，這種方法對節點能量儲備要求較高，整個網絡的成本大幅增加，普通應用環境難以達到該要求;另一種方法是調整節點的布局，使其更加合理。通常情況下后者更易于實現，特別當WSN中部分或全部節點具有移動性時，此方法更具可操作性。

當前，許多研究工作都是圍繞固定節點的WSN展開的，當固定的節點感知到其傳感范圍內的信息后，即將數據通過多跳的方式傳輸到附近的Sink節點。當節點具有移動性后，數據的傳輸會變得更加便捷。然而在一個WSN系統中存在過多的移動節點會導致整個系統變得過于復雜，從而容易失控。因此本文中僅將有特殊性能的Sink節點賦予移動性，使其能滿足系統的需要，被一般傳感節點收集的信息通過多跳的方式傳輸到Sink節點，其移動性加強了網絡對數據處理的能力，減少網絡通信壓力并增強了整個網絡的連通性和傳感覆蓋率。關于移動傳感節點的一些問題不少學者已經展開研究，如文獻[5]考慮了帶移動Sink節點的WSN網絡壽命問題;還有關于節點間通信問題的研究[6]等等。

提高傳感覆蓋率的有效方法之一是隨機布置之后進行有效的位置調整。人工勢場廣泛應用于各種控制策略中，一般來說具體分為兩類，一類是具有吸引能力的勢場，另一類是具有排斥能力的勢場，他們類似地理形態中的山峰與山谷，在其中運動的物質自然是避開山峰而向山谷移動[7]。本文將人工勢場方法用于控制Sink節點移動，主要討論如何提高覆蓋率，即提高被傳感節點覆蓋的面積與監測的整個面積之比(ROI)，即是利用節點間的相對位置關系產生的力來推動移動節點變換位置從而提高整個網絡的傳感覆蓋率[8]。

本文主要內容安排如下:在第1部分整體概述的前提下，第2部分介紹采用的WSN系統結構;緊接著對系統中各個組成部分間的人工勢場及其產生的控制力進行描述，在此基礎上給出節點移動的算法，最后第5部分依據本文提出的算法進行仿真研究。

1 系統結構

1.1 WSN系統結構

構建一個良好的系統結構是高效工作的前提，不同的網格劃分方法決定了系統的結構。通常根據網格形狀的不同大致可分為方形網格和菱形網格(三角形或六邊形)兩類[9]。本文采用正六邊形網格劃分方法，此方法在同樣的面積中節點數更少;在保證系統的連通性及傳感覆蓋率等要求的前提下，整個系統能耗較小[10]。如圖1所示，傳感節點位于正六邊形的中心，圓形是該節點的傳感范圍，其半徑是節點傳感半徑r;虛實線表示的是圓形的內接正六邊形，各六邊形之間無重疊區域，節點之間通信路徑用虛線表示。由幾何知識知，任意兩個節點之間的通信距離d相等且。圖1顯示每個節點可以和周圍6個鄰居節點通過單跳的方式直接通信[11]。

圖1 正六邊形網格劃分的WSN結構

不失一般性地，當節點傳感半徑為r時，設通信半徑為R(R=2r)，每個節點在其傳感范圍內收集數據，而在通信范圍內傳遞數據。通常在WSN中，發送和接收數據消耗大部分的節點能量，因此尋找有效的通信路徑顯得十分必要。在正六邊形網格劃分結構中從一個節點到另一個節點的直線距離為(如圖1所示)，虛線所示的三角形即節點間信息傳輸所走路徑，即信息傳輸過程中單跳距離為。正六邊形網格劃分方法能較好地保持系統的連通性及傳感覆蓋率。因此借助此結構每個節點能直接跟周圍6個節點進行信息傳輸(包括發送和接收數據)。

1.2 Coverage傳感覆蓋率

傳感覆蓋率的概念在文獻[12]中提出，通常傳感覆蓋率一般定義如下:，其中C為覆蓋率，Ai為節點i的有效覆蓋的面積，N為節點數，A為待監測的整個區域，ri是節點i的傳感半徑，因此有。本文也將在此基礎上進行研究。

2 人工勢場方法

眾所周知，異性電荷相吸引，同性電荷相排斥。由于節點間需要保持理想距離，當節點間實際距離小于理想距離時兩節點看做同種電荷，相互排斥，當節點實際距離大于理想距離是看做異性電荷，相互吸引以便節點間保持理想距離。因此，在此假設前提條件下，本文將移動Sink節點與周圍環境看做電荷間的電場關系，WSN中各節點間的人工勢場便可以作如下描述。

2.1 移動Sink節點和普通節點之間的人工勢場

在理想的系統結構中，節點的分布情況應如圖1所示，因此，在初始隨機部署之后可以通過移動Sink節點的位置調節來改善節點分布情況以提高系統傳感覆蓋率。Sink節點和普通節點之間的人工勢場描述如下:

其中VI(xij)是第i個節點和第j個節點之間的勢場，稱為第i個節點和第j個節點之間的勢能函數。xij=xi－xj表示第i個節點和第j個節點之間的距離，αI和βI是正的標量參數，d1是標量，描述節點之間理想距離，d0表示兩個節點之間能相互產生斥力或引力的最大距離。

當0＜‖xij‖＜d1時，兩個節點視為同種電荷，相互間產生排斥力，而當d1≤‖xij‖≤d0時，相互吸引。根據前文介紹的WSN系統結構知，通過節點之間的排斥或吸引力調節它們之間的相互位置，該勢場產生的虛擬力為:

當‖xij‖≥d0時勢場為零，即當Sink節點與普通節點保持理想距離d1時，或相互間距離大于d0時，互相沒有排斥或吸引力，當小于理想距離時，產生排斥力。距離越小，相互的排斥力就越大;反之，節點之間距離大于理想距離為相互吸引，隨著距離的增大吸引力逐漸增大，直到超出傳感范圍d0，d0可以根據實際情況作出調節，本文仿真中取d0=2R'+2r(R'為Sink節點通信半徑)。

2.2 Sink節點間的人工勢場

設r'為Sink節點的傳感半徑，其通信半徑R'滿足R'=2r'。Sink節點通信能力能達到其管轄區域的全部范圍(即半徑為R'的圓能覆蓋其整個監測區域)，但各個Sink節點之間沒有必要重復覆蓋，因此，各Sink節點之間保持的理想距離應不小于2R'。

因此，對于移動Sink節點i和j之間的人工勢場表示為:

其中VS為Sink節點間的人工勢場，xij為第i個Sink節點和第j個Sink節點之間的距離，αs是正的標量參數。該勢場產生的虛擬力為:

2.3 Sink節點與邊界間的人工勢場

這里考慮Sink節點和傳感區域邊界之間的人工勢場，該人工勢場定義為:

其中Vo表示節點和邊界之間的人工勢場，參考電磁場相關知識，κo是一正向量系數，Q為電荷總量，式ril=xi－ol中xi和ol分別為節點及邊界線上某點的位置，根據電磁場的理論，該兩點之間產生的力為:

fo為Vo對于xi的梯度，則為Sink節點與邊界中某點之間的力。根據式(5)、式(6)知

Fo表示整個邊界與Sink節點之間產生的力:

在二維空間中沿x軸和y軸的力分別為:

lx和ly分別為邊界沿x軸和y軸方向的分量。

勢場Vo僅僅存在于邊界附近，防止Sink節點隨意移動出檢測范圍，根據WSN系統的特點取距邊界距離為r'的帶型區域。

勢場Vo僅存在于邊緣附近以防止Sink節點移出待測區域，根據實際情況，該勢場存在的范圍可人為地設定，但均不影響以下的理論分析。

同理，當檢測區域邊緣為為曲線時，進行相應的曲線積分，也能夠獲得Sink節點和檢測邊緣之間的人工勢場及其產生的力。

3 算法介紹

本文提出的算法希望利用Sink節點的移動來提高傳感覆蓋率，但如果在wsn網絡中太多節點具有移動功能，整個網絡結構變得復雜多變，反而不利于網絡分析，于是在整個網絡中Sink節點所占的比例應當合適，不失一般性地設系統中普通節點和Sink節點的傳感半徑與通信半徑分別滿足R=2r以及R'=2r'，則在節點分布理想的WSN系統中，Sink節點的數量與普通節點的數量之比應滿足一定的數量關系以便系統更高效地完成任務。

由圖2知如果按照正六邊形網格劃分方法部署節點，理想情況下每個節點的有效覆蓋面積為傳感范圍圓的內接正六邊形，其面積為，其中 r為該節點的傳感半徑。因此，若整個傳感網絡節點個數為n，則按照理想部署情況分析，其有效檢測面積為。而通常為了保證監測數據的全面性及冗余性，因此在實際應用中，檢測區域面積S和傳感節點數量n需要滿足:

圖2 Sink節點通信范圍

在按正六邊形網格劃分的WSN系統中，Sink節點的通信半徑為2r，如圖2所示，若位置理想，可以覆蓋7個普通傳感節點，若不考慮信息在WSN中傳遞的作用，即將信息傳輸的通信壓力降到最低，由此可知Sink節點不考慮移動功能的情況下，理想的Sink節點個數應為WSN系統中總節點數的1/8，此外，根據實際系統中Sink節點屬性、布置位置及網絡通信情況，作一定的調整便能確定Sink節點所占總節點數量比例。

為了提高傳感覆蓋率的目的，整個系統應該滿足以下條件:

①移動Sink節點的數量適當;

②所有的節點處理為單位質點;

③普通節點的傳感半徑r和通信半徑R滿足如下關系R=2r;

④Sink節點的傳感半徑為r'，通信半徑為R'(R'=2r')。

為了使網絡更加有效，移動Sink節點應具備以下特點:

①Sink節點的移動性;

②對Sink節點提供足夠的能量以便其完成移動的任務;

③高可靠性;

④對Sink節點進行定期維護。

基于以上提到的網絡條件，為提高WSN的傳感覆蓋率，由式(1)～式(10)，利用前文介紹的人工勢場方法對Sink節點進行重新部署。在隨機布置初始位置之后，利用本文介紹的方法使Sink節點移動到無節點覆蓋的區域以便與該區域周邊的節點進行通信，而Sink節點的移動是通過人工勢場產生的力來推動的，如式(1)～式(10)所示。算法步驟如下:

①隨機部署所有節點;

②檢測并計算所有節點位置;

③每個節點檢測其自身鄰居的位置(在其通信半徑內的節點為其鄰居);

④根據式(1)～式(10)，Sink節點計算其承受的綜合人工勢場;

⑤根據人工勢場產生的力使Sink節點移動;

⑥Sink節點是否到達平衡點位置，是，轉到步驟7，否則到步驟4;

⑦結束。

4 仿真實例

在大小為100×100的正方形區域中，當采用傳感半徑r=10，通信半徑R=20的傳感節點時，由式(11)知共需節點40個左右，首先隨機部署這40個節點，其中包括5個移動Sink節點(占節點總數的1/8)，Sink節點傳感半徑r'=2r=20，在式(1)、式(10)的控制下，Sink節點進行移動，直至平衡位置。在圖3和圖4中各節點傳感半徑r=10，通信半徑R=20，用實心圓及其圓心分別表示普通節點的傳感半徑及當前位置，Sink節點傳感半徑、通信半徑及其位置用虛線圓及其圓心表示。Sink節點收集其通信范圍內的一般節點信息，并做簡單處理。圖3為初始隨機部署的情況，圖4為利用本文提出的人工勢場控制方法調節后整個系統的分布情況。從仿真結果能看出來通過Sink節點的移動能有效提高系統傳感覆蓋率。

圖3 隨機部署效果

圖4 移動Sink節點后的分布情況

由于仿真中節點初始位置是隨機的，因此每次仿真結果并不相同，本文經過多次仿真求平均值來進行整體控制效果比較，統計結果如下:

平均覆蓋率 Sink節點移動前 Sink節點移動后1 次 62.5% 83.3%10 次 58.7% 82.5%30 次 60.8% 83.9%50 次 61.3% 82.7%

5 總結

人工勢場方法具有描述環境能力強的特點，能處理各種不同物體之間的相互關系，因此可以借助此方法控制移動節點到理想位置。本文正是利用此方法對WSN系統中Sink節點進行控制以提高系統的傳感覆蓋率。采用此方法不必事先預知環境信息，在短時間內能達到滿意的控制效果。仿真結果證明了此方法的有效性。

在整個系統中同時存在多個不同的人工勢場，因此各勢場間的協調性需要通過參數的調整來完成，根據具體實際情況在強調某種勢場的情況下兼顧其他勢場的影響，最終達到整體協調，改善系統性能的目的。

[1]Ghosh A，Das.Coverage and Connectivity Issues in Wireless Sensor Networks:A survey[J].Pervasive and Mobile Computing，Vol.4，No.3，June 2008:303－334.

[2]Meguerdichian S，Koushanfar F，Potkonjak M，et al.Coverage Problems in Wireless Ad-Hoc Sensor Networks[J]IEEE Infocom 2001，Vol 3，April 2001:1380－1387.

[3]Cardei M，Wu J.Coverage in Wireless Sensor Networks[M]Handbook of Sensor Networks.CRC Press，United States of America 2005:10－20.

[4]林祝亮，馮遠靜，俞立，無線傳感網絡覆蓋的粒子進化優化策略研[J].傳感技術學報，2009，22(6):873－877.

[5]Denkovski D，Mateska A，Gavrilovska L.Extension of the WSN lifetime through controlled mobility[C]//Seventh International Conference on Wireless On-demand Network System and Services(WONS)，Kranjska Gora，Slovenia，2010:151－156.

[6]Eylemekici，Yaoyao Gu，Doruk Bozdag.Mobility-Based Communication in Wireless Sensor Networks[J].IEEE Communications Magazine，July 2006:56－62.

[7]Naomi Ehrich Leonard，Edward Fiorelli.Virtual leaders，artificial potentials and coordinated control of groups[C]//Proceedings of the 40th IEEE Conference on Decision and Control 2001:2968－2973.

[8]Howard A，Mataric M J，Sukhatme G S.Mobile sensor network deployment using potential fields:A distributed scalable solution to he area coverage problem[C]//International Conference on Distributed Autonomous Robotic Systems(DARS02)，Fukuoka，Japan，June 2002:299－308.

[9]傅質馨，徐志良，黃成，吳曉蓓，無線傳感器網絡節點部署研究[J].傳感器與微系統，2008，27(3):116－120.

[10]趙國炳，陳國定，張奇偉，一種無線傳感器網絡覆蓋優化方法[J].機電工程，2009，26(6):80－82.

[11]王佳，WSN中基于改進蟻群算法的移動Agent路徑規劃[J].傳感技術學報，2011，24(4):609－613.

[12]D.W.Gage.Command control for many-robot systems[C]//AUVS－92，the Nineteenth Annual AUVS Technical Symposium:22－24.