改進的非均勻有向傳感器網絡節點部署方法*

譚 勵，楊朝玉，楊明華，胡計鵬

（1.北京工商大學計算機與信息工程學院，北京100048；2.第二炮兵裝備研究院，北京100094）

有向傳感器網絡是一種特殊的移動傳感器網絡，其節點不僅具有方向性，而且具有移動能力。

1 研究現狀

1.1 有向傳感器網絡的部署

移動傳感器網絡是一種全新的信息獲取與處理技術，其網絡自組織、節點自移動，且低成本、低功耗的優勢使其在多個領域得到了廣泛應用。例如在環境領域，為了改善與大眾生活健康息息相關的空氣質量，構建兼具靜止、可移動裝置的混合傳感器網絡體系用于室內監測［1］；在基礎設施中，基于信息物理融合系統CPS（Cyber-Physical System）分布式可計算無線傳感器網絡的出現，為智能建筑該方向的相關研究正逐漸擴寬與深入，尤其是針對節點方向性的部署問題。文獻［4］以進行初期部署后出現的網絡空洞為基礎，構建Voronoi多邊形，控制節點下一階段的移動位置；文獻［5］從安全應用角度出發，針對邊界問題提出柵欄覆蓋部署策略；文獻［6］提出一種基于虛擬勢場的有向傳感器網絡覆蓋優化算法PCAFD（virtual Potential field based Converage Algorithm For Directional sensor networks）用于改進邊界情況和網絡優化過程中出現的節點往復運動現象，FFLRCA（Fictitious Force based Low Redundancy Coverage-enhancing Algorithm）算法用于網絡進入穩定狀態后根據節點及其冗余子集進行能量和位置上的調整；文獻［7］采用分布式啟發式算法，優化有向K覆蓋問題，提高覆蓋性能。此外，還有諸如最小代價算法［8］、啟發式算法［9］、路徑覆蓋算法［10］等應用于傳感器網絡部署策略。

現有的有向傳感器網絡部署算法，主要解決了部署過程中的漏洞，能夠較好的提高覆蓋率。然而這些方法對于待覆蓋區域缺乏分析，難以滿足一些區域中的復雜部署要求。尤其是通過對待部署區域的分析發現，針對不同區域具有不同部署密度要求的有向傳感器網絡算法具有重要的實用意義。

本文提出了一種改進的非均勻有向傳感器網絡節點部署方法PFNDA（Potential Field based Non-uni?form Distribution Algorithm），能夠適用于待部署區域的非均勻部署需求，針對區域內的優先監測塊，引入“部署中心”對象模型，通過部署中心與傳感器節點之間的相互作用，提高區域內的覆蓋質量。

2 改進的非均勻有向節點部署算法

2.1 概念描述

2.1.1 部署中心

定義1部署中心范圍。規定以重點監測區域中心為Sc圓心，該區域與中心的最遠距離Rc為半徑劃定一圓形區域，該區域即為部署中心范圍。

圖1 部署中心

定義2部署中心密度。在節點集合覆蓋能力不足的情況下，為保證節點盡可能廣地分布，節點集合整體覆蓋密度將有所下降。但對于部署中心而言仍需要保證足夠的覆蓋能力。因此，在部署中心范圍內，將采取和其它區域不同的節點分布情況，這一控制系數則為部署中心密度。

2.1.2 有向節點

定義節點模型為帶有虛擬力模型，由五元組＜p,L,α,θ,η＞表示。其中p表示節點的定位位置，L表示最遠監測距離，α表示節點當前監測視角中軸指向角度，θ表示監測所能及的最大視角角度，η表示目標節點的鄰近節點集合。

圖2 有向節點

在非部署中心區域，目標節點與其鄰近節點集合需要考慮兩方面，其一是指向角度，其二是覆蓋范圍。當相鄰節點間覆蓋重疊量達到一定程度，則需要目標節點變換角度，提高覆蓋率。

而在部署中心區域，覆蓋重疊將作為次要考量，甚至可以忽視這一因素，對于非理想條件下，這種覆蓋重疊甚至可以用于提升覆蓋質量。指向角度作為主要的考量因素，目標節點的指向優先與部署中心有關。

2.2 算法模型

與均勻有向節點部署方法相比，非均勻部署方法中節點間的斥力作用同樣基于質心點模型［11］。在此基礎上，區別主要體現在移動節點在靠近部署中心時刻其相關屬性發生變化。

圖3 算法模型示意圖

部署中心位置設為Sc，部署中心范圍半徑設為Rc。節點質心位置設為Sn，節點質心半徑設為Rn。主要屬性如下：

2.2.1 矢量引力

設區域內存在任意節點Pi，另有任一節點為Pj，則目標節點Pi受到的作用力Fi表示如下：

當節點Pj屬于目標節點Pi的鄰居節點集合Ni內且兩節點間距離小于節點產生斥力的最大距離L斥時，目標節點受到該類節點產生的斥力向量；當節點Pj屬于目標節點Pi的鄰居節點集合內且兩節點間距離介于節點產生引力的最小距離L引和節點產生斥力的最大距離L斥之間時，目標節點受到該類節點產生的引力向量；其它情況則不對目標節點產生作用力。

而節點與部署中心的作用力則相對簡單。目標節點質心Sn(xn,yn)與部署中心Sc(xc,yc)的矢量距離為：

2.2.2 非均勻斥力

區域內活動的目標節點依據其與鄰近節點的距離受到不同方向的虛擬斥力，且該值唯一。當目標節點在部署中心范圍內時，為了獲得更好的覆蓋質量，根據需要調整虛擬斥力值。

若節點Pi在部署中心范圍內，則調整后的節點Pi的作用力Fi′表示為

通過對參數fc的控制，減小節點模型的虛擬斥力以達到在部署中心范圍內的節點集合分布更加密集。

2.2.3 節點方向控制

根據目標節點與部署中心距離d(Sn,Sc)判定目標節點的方向控制。當目標節點在部署中心范圍外時，節點方向指向與其鄰近節點集合相關，以提高覆蓋率、減少重疊為主要目的，即當目標節點與鄰近節點覆蓋區域重疊時，節點方向變換直至沒有重疊為止。為簡化該步驟，可將圓周劃分為多個等分區域，在目標節點變換方向時可按區域固定轉動一定角度。當目標節點在部署中心范圍內時，方向將以部署中心點為基準，使節點中軸線與部署中心點在同一條直線，以保證目標節點的視角中心指向部署中心區域。

2.2.4 部署質量評價

對于部署中心范圍外的部署效果采用覆蓋率評價，而對于部署中心內部涉及覆蓋面積、覆蓋方向、覆蓋重疊多重考量，故使用部署質量這一指標進行評估。針對重點關注的覆蓋面積問題，本次實驗主要考量以下兩點：

①有效節點數

該指標以實際應用角度出發，出于重點監測區域的產生使部分涉及該區域的節點監測目的不再是盡可能全面地監測更多區域，而改為優先監測以重點監測面積中心起始向外擴散至指定范圍。為此本次實驗認定重點區域內執行優先監測任務的節點即為有效節點，以此判定算法在非均勻部署條件下部分區域的重視程度。

②覆蓋率

該指標通過節點在部署中心范圍內覆蓋面積與部署中心范圍全面積之比進行判斷。設總比面積為CN，單一節點面積為Cp，則覆蓋面積指標表示為：

矢量引力和非均勻斥力屬性均是有條件的，即在部署中心范圍內才會生效，這表明范圍的節點其一切調度策略均保留一般情況的有向傳感器網絡部署策略，故而對于范圍外的覆蓋質量評估不進行對比分析考察。

2.3 PFNDA算法描述

根據上述概念及模型屬性分析，得到的改進的非均勻有向節點部署算法在保證原有網絡覆蓋質量的前提下，提高方向屬性上的有效監測質量，使傳感器網絡更好地實現監測與通信功能。

算法偽代碼如下：

算法具體步驟如下：

①初始化：節點根據其自身屬性，關聯其它節點，構建鄰居節點集合。由于部署中心與節點基本具備相同屬性，同樣需要創建類似的節點集合。

②矢量引力：節點與其鄰居節點集合內的所有節點依次判斷之間距離，根據判斷條件得到最終目標節點受到的虛擬作用力矢量。部署中心同樣與其節點集合進行判斷，但部署中心本身不會被施加任何作用力，符合條件的周邊節點通過自身位置得出受到的虛擬引力矢量。

③非均勻斥力：存在于部署中心的有效感知范圍內部的傳感器節點在判斷虛擬作用力時除去與鄰居節點集合之間的計算外，還會受到來自部署中心的作用力參數控制的影響。部署中心范圍內節點之間的虛擬斥力數值將會經由該參數發生變動，而其他區域維持不變。

④穩定狀態：重復步驟①～步驟③直至整體網絡結構達到穩定狀態則結束部署。

3 實驗及結果分析

3.1 實驗環境

本實驗是在改進后的The ONE仿真器環境的基礎上進行的。仿真器環境以節點為基本單位，不同的節點賦予各自不同的性能，或遵循不同的協議，并將這些屬性建立在移動模型上，最終通過仿真環境的GUI圖形界面體現節點分布、移動、通信的性能表現。

改進后的The ONE仿真器屏蔽了路徑規劃模塊，節點將不再按路徑規劃移動，而是呈現自由移動的狀態。在這樣的環境下的性能展示與評估可以排除其它外在因素，而只針對節點自身，從而更加清晰直觀。

3.1.1 實驗需求

針對部署中心需要考慮面積覆蓋和方向覆蓋兩個方面。對于面積覆蓋本實驗需要達到相對于非部署中心區域，部署中心區域的覆蓋率有明顯提升，而且需要增加覆蓋質量（為防止節點自身故障而引起的覆蓋或連通問題而特意留有一定程度的重疊覆蓋）系數以進一步加強面積覆蓋。在方向覆蓋上則要求在部署中心圍繞范圍內的節點方向均面向部署中心，保證部署中心為最主要監測焦點。

3.2 結果分析

本次實驗設定在規定區域內任意設定一坐標位置為部署中心點并隨機拋灑N個節點。根據實驗要求記錄了一定時間內節點部署活動軌跡及其對應的覆蓋率變化軌跡，如圖4所示，其中t為以節點運動開始為基準的時間增值。

圖4 節點變化軌跡

但僅有這一屬性仍稍有不足。在保證部署中心范圍內的所有移動節點均指向中心點的同時，也意味著當部署中心的鄰近節點達到穩定狀態時，未被覆蓋的部分，即覆蓋空白區域也達到了穩定狀態，而且相比非部署中心范圍而言更加穩定。這是由于臨近節點的監測方向不再放生改變所引起的。因而在原有基礎上，部署中心還增加了非均勻斥力屬性。

非均勻斥力屬性在節點的方向監測性上面并沒有什么表現，然而該屬性使部署中心區域內覆蓋節點之間的空洞大幅減少，幾乎可以達到完全覆蓋的效果。當然，這是以增加部分覆蓋重疊同時犧牲一定的覆蓋面積為前提的。

3.3 對比分析

通過上述結果表述，為進一步深化分析，本文采用與覆蓋優先算法PFPCA（Potential Field based Priority Coverage Algorithm）［12］進行相關有效節點數和覆蓋率上的對比分析。

3.3.1 對比算法描述

基于虛擬勢場的覆蓋優先算法PFPCA用于實現移動傳感器網絡的自動化部署。該算法擺脫了節點自身有關動能的約束，使節點運動只與最終虛擬合力是否為零有關，節點的旋轉只與合力沿圓周的切線方向向量有關。

3.3.2 有效節點數

本節記錄了兩種算法在同等實驗條件（如表1所示）下存在于部署中心范圍內的節點數量以時間為基準的變化軌跡，如圖5所示。

表1 實驗要求列表

圖5 有效節點數變化軌跡

根據圖表中兩者間的比較，可以看到PFPCA算法并未對范圍內的部署節點采取特殊的方向控制，節點的方向屬性變化完全取決于鄰近節點狀態，因此該算法下有效節點數量呈現不穩定的隨機態勢。而改進后的PFNDA算法在矢量引力影響范圍內，節點數量不再只能是隨機出現有效方向，而是在屬性控制下全部指向部署中心。而在引入非均勻斥力后，帶來部署中心范圍內的節點最大存在數量的增加，更是呈現大幅度提升。

3.3.3 覆蓋率

本節記錄了兩種算法在同等實驗條件（如表1所示）下部署中心范圍內（部署中心范圍外的部署方法并未受到改進的屬性影響，故不在此進行比對）以時間為基準的覆蓋率變化軌跡，如圖6所示。

圖6 覆蓋率變化軌跡

從圖6可以看出，改進后的算法在達到穩定狀態時覆蓋率相比PFPCA算法有明顯提高，這是因為在增加了非均勻斥力屬性后，由于節點間間隙的減小而導致覆蓋效率有了一定程度的增長。

4 結束語

針對傳感器網絡重點區域重點覆蓋的實際需求，提出了一種改進的非均勻有向傳感器網絡節點部署方法，經由本文實驗對比表明，通過對原有的有向節點部署方法的改進，該算法優化了在處理局部重點監測時有可能發生的監測面積和方位監測不足的問題。下一步可引入例如移動節點的能源持續性和休眠機制，部分區域的具體有效監測指標等更為詳細的技術參數，對有向節點部署方法做進一步的優化和提升。

［1］Xiang Yun，Piedrahita R，Dick R P，et al.A Hybrid Sensor System for IndoorAirQualityMonitoring：Proceedings-IEEEInternationalCon?ferenceonDistributedComputinginSensorSystems，2013［C］//Cam?bridgeMA，Unitedstates：IEEEComputerSociety，2013：96-104.

［2］高治軍，王洪玉，王鑫，等.智能建筑室內環境分布式可計算WSN任務調度研究［J］.傳感技術學報，2014，27（3）：378-382.

［3］胡永利，孫艷豐，尹寶才，等.物聯網信息感知與交互技術［J］.計算機學報，2012，35（6）：1147-1163.

［4］Liang Chiukuo，Chung Chengyen，Li Chuangfeng.A Virtual Force Based Movement Scheme for Area Coverage in Directional Sensor Networks：Proceedings-2014 10th International Conference on In?telligent Information Hiding and Multimedia Signal Processing，2014［C］//Kitakyushu，Japan：Institute of Electrical and Electron?ics Engineers Inc，2014：718-722.

［5］Wang Zhibo，Liao Jilong，Cao Qing，et al.Barrier Coverage in Hy?brid Directional Sensor Networks：Proceedings-IEEE 10th Interna?tional Conference on Mobile Ad-Hoc and Sensor Systems，2013［C］//Hangzhou，China：IEEE Computer Society，2013：222-230.

［6］戴寧，毛劍琳，付麗霞，等.基于虛擬勢場的有向傳感器網絡覆蓋優化算法［J］.計算機應用研究，2014，31（3）：905-907.

［7］張美燕，蔡文郁.無線視頻傳感器網絡有向感知K覆蓋控制算法研究［J］.傳感技術學報，2013，26（5）：728-733.

［8］Osais Y，St-Hilaire M，Yu F R.The Minimum Cost Sensor Place?ment Problem for Directional Wireless Sensor Networks：IEEE Ve?hicular Technology Conference，2008［C］//Calgary，AB，Canada：Institute of Electrical and Electronics Engineers Inc.，445 Hoes Lane/P.O.Box 1331，Piscataway，NJ 08855-1331，United States，2008：1-5.

［9］Shankarachary Ragi，Hans D Mittelmann.et al.Directional Sensor Control：Heuristic Approaches［J］.IEEE Sensors Journal，2015，15（1）：374-381.

［10］陶丹，馬華東，劉亮.視頻傳感器網絡中路徑覆蓋增強算法研究［J］.電子學報，2008，36（7）：1291-1296.

［11］陶丹，馬華東，劉亮.基于虛擬勢場的有向傳感器網絡覆蓋增強算法［J］.軟件學報，2007，18（5）：1152-1163.

［12］Tan Li，Chen Yucheng.et al.Priority Coverage Algorithm and Per?formance Simulation for Node Deployment in Directional Sensor Networks［J］.Sensor Letters，2014，12（2）：275-280.