基于二維虛擬力的陸軍地面通信網(wǎng)部署

段宇江，祁志民，程 賓，徐海亞，段笑笑

（北方自動(dòng)控制技術(shù)研究所，太原 030006）

0 引言

現(xiàn)代戰(zhàn)爭(zhēng)常發(fā)生在一些復(fù)雜未知的區(qū)域，這些區(qū)域或者環(huán)境非常惡劣，人無(wú)法自由行動(dòng)；或者面對(duì)陌生的環(huán)境，人無(wú)法正確辨識(shí)周圍。一旦遇到這些情況，我軍在新區(qū)域的通訊網(wǎng)絡(luò)很難及時(shí)迅速地展開部署，可能因此失去了戰(zhàn)略先機(jī)。故提出搭載有無(wú)線基站通信節(jié)點(diǎn)的無(wú)人車作為地面移動(dòng)的通信中轉(zhuǎn)站，是在陸軍作戰(zhàn)領(lǐng)域的一種創(chuàng)新。

無(wú)人節(jié)點(diǎn)車是一個(gè)分布于二維空間、且由具有較強(qiáng)機(jī)動(dòng)能力的地面移動(dòng)通訊基站［1］。可在指定地區(qū)的空域，完成對(duì)無(wú)人節(jié)點(diǎn)車的拋撒，拋撒位置受到高空復(fù)雜天氣條件的影響，時(shí)常出現(xiàn)部分無(wú)人節(jié)點(diǎn)車“逃逸”目標(biāo)區(qū)域和過(guò)于聚集的現(xiàn)象，此時(shí)通信效能受到嚴(yán)重影響。為了有效防止“逃逸”與過(guò)于聚集問(wèn)題，本文致力于研究二維移動(dòng)地面通信網(wǎng)的部署問(wèn)題，即目標(biāo)均勻覆蓋問(wèn)題，即通過(guò)制定一種約束策略，讓二維移動(dòng)節(jié)點(diǎn)能夠自組織地形成對(duì)目標(biāo)區(qū)域的均勻覆蓋，保證目標(biāo)區(qū)域的每一個(gè)點(diǎn)都處于通信網(wǎng)絡(luò)范圍之內(nèi)。

面對(duì)這種問(wèn)題的出現(xiàn)，提出一種基于二維虛擬力的自組織覆蓋算法［2］。除去傳統(tǒng)虛擬力（Traditional Virtual Force，TVF）（通常指代斥力和引力）之外，引入了中心引力（Central Gravitation，CG）和邊界約束力（Border Constraint Force，BCF）兩種約束力作用于無(wú)人節(jié)點(diǎn)車的每一個(gè)節(jié)點(diǎn)，在防止節(jié)點(diǎn)“逃逸”的同時(shí)，使相對(duì)聚集的節(jié)點(diǎn)分散開。引入節(jié)點(diǎn)間距離的閾值、邊界節(jié)點(diǎn)與邊界距離的閾值實(shí)現(xiàn)對(duì)感興趣區(qū)域的均勻化覆蓋。

首先列舉課題研究的一些假設(shè)條件。即使有些前提與實(shí)際情況可能不相符合，但基于這些假設(shè)所構(gòu)建的模型能為新型應(yīng)用提供啟發(fā)式的理論思維，稍微修改便能應(yīng)用于具體的實(shí)戰(zhàn)場(chǎng)景中。假設(shè)條件如下：

1）假定節(jié)點(diǎn)的通信半徑為確定性的、全向的圓形模型。如此，每個(gè)節(jié)點(diǎn)都會(huì)產(chǎn)生相同大小的通信球。

2）每個(gè)節(jié)點(diǎn)能從它本身或者它的移動(dòng)載體上所附帶的北斗等定位系統(tǒng)上獲得自己的絕對(duì)坐標(biāo)信息。

1 二維虛擬力系統(tǒng)

1.1 基本虛擬力算法擴(kuò)展

傳統(tǒng)的虛擬力算法［3］是由勢(shì)場(chǎng)法［4］和圓盤理論［5］發(fā)展而來(lái)。它在節(jié)點(diǎn)之間同時(shí)定義了互相牽制的吸引力和排斥力。

在虛擬力算法部署過(guò)程中，為了保持一個(gè)緊密的結(jié)構(gòu)，不讓移動(dòng)節(jié)點(diǎn)個(gè)體“逃離”目標(biāo)區(qū)域，定義每個(gè)節(jié)點(diǎn)都會(huì)吸引周圍節(jié)點(diǎn)使其不離開自己身邊。模擬物理世界，稱其為吸引力。在節(jié)點(diǎn)互相處于通信范圍內(nèi)的前提下，相對(duì)距離越長(zhǎng)，節(jié)點(diǎn)之間互相靠近的渴望就越強(qiáng)烈，因而產(chǎn)生越大的吸引力。另一方面，為了防止節(jié)點(diǎn)之間距離太近而生成不必要的覆蓋區(qū)域重疊，定義了相互之間的排斥力，從而保證了節(jié)點(diǎn)不會(huì)過(guò)于擁擠密集。排斥力能夠使節(jié)點(diǎn)避免碰撞，從而符合了經(jīng)濟(jì)和安全要求。

事實(shí)上，虛擬力機(jī)制將個(gè)體移動(dòng)的通信網(wǎng)絡(luò)看成是包含力和速度的一個(gè)虛擬物理系統(tǒng)。為了設(shè)計(jì)的簡(jiǎn)單化，通常將某一時(shí)刻節(jié)點(diǎn)所受合力的方向看成是下一時(shí)刻節(jié)點(diǎn)運(yùn)動(dòng)的物理方向。最終，虛擬力機(jī)制會(huì)使得節(jié)點(diǎn)群變得相當(dāng)穩(wěn)定和緊湊。當(dāng)某節(jié)點(diǎn)因?yàn)槟承┨厥庠蚴r(shí)，由于局部的受力不均，剩下的節(jié)點(diǎn)會(huì)自動(dòng)移動(dòng)填補(bǔ)空當(dāng)，直到一個(gè)新的收斂狀態(tài)。

在二維空間中，每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)著2個(gè)同心圓。首先，每個(gè)節(jié)點(diǎn)能夠通過(guò)無(wú)線基站與一定距離內(nèi)的鄰居節(jié)點(diǎn)直接通信，該距離定義為通信半徑Rc，對(duì)應(yīng)的通信區(qū)域定義為通信圓。其次，稱之為平衡圓，以Rb（0≤Rb≤Rc）為半徑，其中Rb為吸引力和排斥力的分界。每個(gè)通信節(jié)點(diǎn)對(duì)平衡圓以外但是通信圓以內(nèi)的鄰居節(jié)點(diǎn)，僅產(chǎn)生引力作用。

虛擬力規(guī)則提煉如下：節(jié)點(diǎn)之間的距離越近（遠(yuǎn)），彼此產(chǎn)生的排斥力（吸引力）越大。即，距離平衡球體表面的距離越遠(yuǎn)，受到虛擬力場(chǎng)的影響越大。當(dāng)節(jié)點(diǎn)正好落于彼此雙方平衡球體表面時(shí)（前提是網(wǎng)絡(luò)節(jié)點(diǎn)同構(gòu)），斥力與引力都為0。

1.2 算法演進(jìn)

首先定義基于虛擬力的節(jié)點(diǎn)模型。

定義1 節(jié)點(diǎn)模型可以用一個(gè)六元組＜s，R，v，ns，F(xiàn)，f ＞ 表示。其中 s（x，y）表示節(jié)點(diǎn)的坐標(biāo)。R={Rc，Rb}為節(jié)點(diǎn)自身的半徑屬性集，即產(chǎn)生的兩個(gè)同心圓的半徑。v表示節(jié)點(diǎn)在二維空間中的運(yùn)動(dòng)速度。f為二值型變量，1表示節(jié)點(diǎn)處于目標(biāo)區(qū)域之內(nèi)，反之則為-1。如果兩個(gè)節(jié)點(diǎn)之間距離小于Rc，稱為鄰居節(jié)點(diǎn)。Js表示節(jié)點(diǎn)s的鄰居節(jié)點(diǎn)集合，計(jì)算公式為

F={TV}為節(jié)點(diǎn)s產(chǎn)生的力場(chǎng)，后面會(huì)給出力的詳細(xì)說(shuō)明與定義。

定義2 對(duì)于二維空間中任意兩個(gè)處于通信范圍內(nèi)的通信節(jié)點(diǎn)s1（x1，y1）和s2（x2，y2），歐氏距離為

令s1對(duì)s2施加的傳統(tǒng)虛擬力（Traditional Virtu-的方向由虛擬力的類型決定，大小由式（3）計(jì)算得到：

其中，k表示放大指數(shù)，用以放大與平衡點(diǎn)距離的影響。α用來(lái)確保方程為增函數(shù)，在此給α賦值為10。式（3）計(jì)算所得虛擬力使得相鄰節(jié)點(diǎn)朝其平衡圓圓周移動(dòng)。每個(gè)通信節(jié)點(diǎn)通過(guò)綜合計(jì)算二維空間中與鄰近節(jié)點(diǎn)的位置關(guān)系，自動(dòng)調(diào)整自己的當(dāng)前位置，從而產(chǎn)生一個(gè)高耦合網(wǎng)絡(luò)結(jié)構(gòu)。通過(guò)對(duì)Rb的調(diào)整，可以讓整個(gè)部署結(jié)果變得相對(duì)松散或緊湊。

傳統(tǒng)的虛擬力算法通常是假設(shè)節(jié)點(diǎn)群初始分布較為密集，通過(guò)擴(kuò)散使得網(wǎng)絡(luò)均勻部署開來(lái)。然而實(shí)際應(yīng)用中，節(jié)點(diǎn)通常隨機(jī)散布在二維空間里并通過(guò)移動(dòng)以尋找目標(biāo)區(qū)域。由此基礎(chǔ)上實(shí)現(xiàn)的傳統(tǒng)虛擬力算法通常會(huì)造成網(wǎng)絡(luò)分割或者覆蓋漏洞，需要進(jìn)一步地調(diào)整讓密集區(qū)域更松散或者稀疏區(qū)域更緊湊。傳統(tǒng)虛擬力算法在此情況下表現(xiàn)得并不好，因?yàn)楣?jié)點(diǎn)之間的地位是對(duì)等的，且先驗(yàn)知識(shí)有限，它們并不知道其他個(gè)體區(qū)域的覆蓋密度，所以只能通過(guò)局部而非全局信息進(jìn)行決策。

整體協(xié)調(diào)的缺乏帶來(lái)兩個(gè)潛在問(wèn)題。首先，目標(biāo)區(qū)域可能不會(huì)被很好地覆蓋。隨機(jī)拋撒和無(wú)外界條件干預(yù)的自適應(yīng)部署方式，可能會(huì)產(chǎn)生對(duì)目標(biāo)或大或小的偏移量。其次，即使前面的問(wèn)題得到解決，節(jié)點(diǎn)最終仍有可能部署不均勻。極端情況下，即使網(wǎng)絡(luò)整體在虛擬力的作用下處于平衡狀態(tài)，局部仍有可能出現(xiàn)多處網(wǎng)絡(luò)分割。除了傳統(tǒng)虛擬力TVF，本章定義了中心引力CG，使得部署過(guò)程更加合理和有效。

定義3 CG定義為目標(biāo)區(qū)域?qū)?jié)點(diǎn)群的正面吸引力，具體可參照傳統(tǒng)勢(shì)場(chǎng)法，比如歐氏距離相關(guān)函數(shù)，將CG定義為與TVF相同量級(jí)常量。

二維空間中通信節(jié)點(diǎn)隨機(jī)運(yùn)動(dòng)以搜索目標(biāo)區(qū)域。一旦目標(biāo)確認(rèn)，通信節(jié)點(diǎn)將朝著目標(biāo)產(chǎn)生的CG方向運(yùn)動(dòng)，同時(shí)還會(huì)將目標(biāo)的坐標(biāo)位置信息通知給其他同伴。如此，節(jié)點(diǎn)群通過(guò)CG被吸引到目標(biāo)區(qū)域中來(lái)。

另一方面，分布式部署策略為非中心控制型算法。由于個(gè)體知識(shí)的限制，僅由TV形成的緊耦合結(jié)構(gòu)很有可能包含密度不均勻的區(qū)域。然而這種均勻分布是有較大實(shí)際意義的。有秩序的編隊(duì)能夠充分利用每一個(gè)節(jié)點(diǎn)的有效覆蓋面積，從而使得整體參與的移動(dòng)節(jié)點(diǎn)數(shù)目大大降低。

部署過(guò)程中，每個(gè)節(jié)點(diǎn)不僅僅只作為一個(gè)產(chǎn)生TVF的勢(shì)場(chǎng)，同時(shí)還通過(guò)EF的方式，作為一個(gè)協(xié)調(diào)器去平衡以自我為中心的局部區(qū)域。為了簡(jiǎn)化，采用歐式距離作為計(jì)算方式。每個(gè)節(jié)點(diǎn)計(jì)算與其所有鄰居節(jié)點(diǎn)的平均距離，然后將該值與鄰居個(gè)體加以比較。如果均值大于個(gè)體值，則產(chǎn)生排斥力；反之則產(chǎn)生吸引力。

定義4 以節(jié)點(diǎn)i為參考，則邊界對(duì)鄰居節(jié)點(diǎn)i產(chǎn)生的邊界約束力表示為該力的大小為

其中，Rb表示節(jié)點(diǎn)i到其所有鄰居節(jié)點(diǎn)距離的平均值。min{d（si，B）}表示節(jié)點(diǎn) i與部署區(qū)域邊界的最短距離。參數(shù)Rth作為引力和斥力分界的邊界距離閾值。區(qū)域邊界對(duì)距離區(qū)域邊界Rth范圍內(nèi)的鄰居節(jié)點(diǎn)僅產(chǎn)生斥力作用，對(duì)［Rth，2Rth］以內(nèi)的鄰居節(jié)點(diǎn)，僅產(chǎn)生引力作用。則式（4）中參數(shù)α和k則與式（2）中相同。

其中Ji表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。

每一個(gè)時(shí)間步長(zhǎng)，根據(jù)節(jié)點(diǎn)與目標(biāo)區(qū)域之間的距離關(guān)系計(jì)算CG，根據(jù)節(jié)點(diǎn)與邊界之間的距離關(guān)系計(jì)算BCF，根據(jù)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的關(guān)系計(jì)算TVF，然后將所有虛擬力矢量相加得到合力。如此，各節(jié)點(diǎn)在合力的驅(qū)使下調(diào)整自身位置一直到自身受力平衡為止，當(dāng)各節(jié)點(diǎn)達(dá)到受力平衡，也意味著整個(gè)網(wǎng)絡(luò)處于穩(wěn)定拓?fù)錉顟B(tài)，進(jìn)而對(duì)所覆蓋的目標(biāo)區(qū)域執(zhí)行感知任務(wù)。

2 算法描述

基于虛擬力的二維均勻部署算法作為分布式算法，其各樣本節(jié)點(diǎn)并發(fā)執(zhí)行相同的策略，位置調(diào)整同步進(jìn)行。取其中任一節(jié)點(diǎn)i的位置更新算法描述如下所示。

3 實(shí)驗(yàn)驗(yàn)證

本文所做基于虛擬力算法的仿真實(shí)驗(yàn)均在二維場(chǎng)景下進(jìn)行，通過(guò)覆蓋率、逃逸率標(biāo)準(zhǔn)去衡量算法的有效性。覆蓋率表示的是目標(biāo)區(qū)域被網(wǎng)絡(luò)覆蓋的百分比，逃逸率表示“逃”出部署范圍的節(jié)點(diǎn)車數(shù)量，與傳統(tǒng)部署方式形成對(duì)比。在通信網(wǎng)絡(luò)問(wèn)題中，覆蓋率總是首要問(wèn)題之一，因?yàn)橛酶俚墓?jié)點(diǎn)得到更大的覆蓋面積是非常有意義的。

3.1 實(shí)驗(yàn)設(shè)置

在空曠場(chǎng)地內(nèi)選取一片實(shí)驗(yàn)區(qū)域，實(shí)驗(yàn)通信節(jié)點(diǎn)車通過(guò)雷達(dá)信號(hào)完成測(cè)距。50 m×50 m的正方形區(qū)域內(nèi)，隨機(jī)地投放36輛該模擬通信節(jié)點(diǎn)車，通信半徑為5 m，依據(jù)設(shè)計(jì)算法得出合力矢量，并根據(jù)矢量方向運(yùn)動(dòng)。每分鐘記錄一次覆蓋范圍以及部署范圍外的節(jié)點(diǎn)車數(shù)量。

3.2 覆蓋率

實(shí)驗(yàn)中，某一區(qū)域點(diǎn)處于至少一個(gè)及以上通信節(jié)點(diǎn)車通信范圍之內(nèi)，則認(rèn)為網(wǎng)絡(luò)針對(duì)該區(qū)域?qū)崿F(xiàn)了有效覆蓋。采用傳統(tǒng)的覆蓋方法來(lái)計(jì)算網(wǎng)絡(luò)覆蓋率。

其中，Si為通信范圍重疊區(qū)域面積，S為試驗(yàn)區(qū)域面積，g為覆蓋率。

圖1給出了在實(shí)驗(yàn)過(guò)程中，每分鐘記錄的區(qū)域覆蓋率變化情況。實(shí)驗(yàn)顯示，添加了中心引力、邊界約束力虛擬約束條件的虛擬力算法可以達(dá)到對(duì)R區(qū)域的全覆蓋需求。

圖1 虛擬力部署方式覆蓋率變化表

3.3 逃逸率

逃逸率是面對(duì)本文所研究的基于改進(jìn)后的二維虛擬力通信網(wǎng)絡(luò)部署方案，提出的一個(gè)評(píng)價(jià)指標(biāo)，認(rèn)定當(dāng)部署過(guò)程中出現(xiàn)節(jié)點(diǎn)車不在規(guī)定區(qū)域內(nèi)的情況，就出現(xiàn)了“逃逸”。虛擬力改進(jìn)前后的部署過(guò)程逃逸率如表1所示。根據(jù)表中內(nèi)容可以得出，增加了中心引力和邊界約束力后，節(jié)點(diǎn)車的“逃逸”情況得到了明顯的改善。

表1 虛擬力改進(jìn)前后部署過(guò)程逃逸率

4 結(jié)論

通信節(jié)點(diǎn)車從隨機(jī)分布到完成部署過(guò)程中，防止通信節(jié)點(diǎn)車的“逃逸”和過(guò)于聚集現(xiàn)象的發(fā)生，最終實(shí)現(xiàn)對(duì)二維目標(biāo)區(qū)域的均勻化覆蓋是通信節(jié)點(diǎn)車投入實(shí)戰(zhàn)的必要前提和條件。為了很好地解決“逃逸”和過(guò)于聚集問(wèn)題，考慮到節(jié)點(diǎn)可在二維空間中自由移動(dòng)和虛擬力算法的分布式屬性，本文提出并實(shí)現(xiàn)了基于二維虛擬力的自組織覆蓋算法，對(duì)傳統(tǒng)虛擬力算法進(jìn)行了有益擴(kuò)展，引入了中心引力、邊界約束力兩種虛擬約束力，以自適應(yīng)的方式部署在目標(biāo)區(qū)域中。實(shí)驗(yàn)表明，場(chǎng)景中部署是合理有效的。