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

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

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

1 研究現(xiàn)狀

1.1 有向傳感器網絡的部署

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

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

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

2 改進的非均勻有向節(jié)點部署算法

2.1 概念描述

2.1.1 部署中心

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

圖1 部署中心

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

2.1.2 有向節(jié)點

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

圖2 有向節(jié)點

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

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

2.2 算法模型

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

圖3 算法模型示意圖

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

2.2.1 矢量引力

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

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

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

2.2.2 非均勻斥力

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

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

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

2.2.3 節(jié)點方向控制

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

2.2.4 部署質量評價

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

①有效節(jié)點數(shù)

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

②覆蓋率

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

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

2.3 PFNDA算法描述

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

算法偽代碼如下：

算法具體步驟如下：

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

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

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

④穩(wěn)定狀態(tài)：重復步驟①～步驟③直至整體網絡結構達到穩(wěn)定狀態(tài)則結束部署。

3 實驗及結果分析

3.1 實驗環(huán)境

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

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

3.1.1 實驗需求

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

3.2 結果分析

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

圖4 節(jié)點變化軌跡

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

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

3.3 對比分析

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

3.3.1 對比算法描述

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

3.3.2 有效節(jié)點數(shù)

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

表1 實驗要求列表

圖5 有效節(jié)點數(shù)變化軌跡

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

3.3.3 覆蓋率

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

圖6 覆蓋率變化軌跡

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

4 結束語

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

［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］高治軍，王洪玉，王鑫，等.智能建筑室內環(huán)境分布式可計算WSN任務調度研究［J］.傳感技術學報，2014，27（3）：378-382.

［3］胡永利，孫艷豐，尹寶才，等.物聯(lián)網信息感知與交互技術［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］戴寧，毛劍琳，付麗霞，等.基于虛擬勢場的有向傳感器網絡覆蓋優(yōu)化算法［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.