袁萬騰++李亞各

摘要：該文中提出了一種速度可控的虛擬力模型，考慮了節(jié)點(diǎn)運(yùn)動狀態(tài)與虛擬力間的關(guān)系，通過引入速度反饋?zhàn)饔昧?jié)點(diǎn)的運(yùn)動狀態(tài)進(jìn)行控制。該虛擬力模型中節(jié)點(diǎn)的運(yùn)動能夠較為準(zhǔn)確的描述節(jié)點(diǎn)在移動部署過程中的運(yùn)動特征。在此虛擬力模型的基礎(chǔ)上，為了能夠?qū)崿F(xiàn)對興趣點(diǎn)的快速覆蓋，同時維持較好的網(wǎng)絡(luò)連通特性，設(shè)計了一種興趣點(diǎn)覆蓋的移動部署算法。該算法通過節(jié)點(diǎn)設(shè)置標(biāo)志值，避免了因興趣點(diǎn)作用力過大造成節(jié)點(diǎn)分布集中的問題，增大了網(wǎng)絡(luò)通信覆蓋范圍，維持了較好的網(wǎng)絡(luò)連通性。

關(guān)鍵詞：無人機(jī)網(wǎng)絡(luò)；網(wǎng)絡(luò)部署；虛擬力；覆蓋

中圖分類號：TN929 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）03-0056-04

Deployment Algorithm for UAV Network

YUAN Wan-teng LI Ya-ge

（Xian Aeronautics Computing Technique Research Institute， AVIC， Xian 710086， China）

Abstract：In this paper， a speed controllable virtual force model is proposed， Considering the relationship between the node motion state and virtual force， the speed feedback force is introduced to control the motion state of node. The movement of nodes in the virtual force model can accurately describe the motion characteristics during the process of node in mobile deployment. Based on the proposed virtual force model， in order to realize the rapid coverage of POI， at the same time maintain good connectivity， this paper designs a point of interest coverage mobile deployment algorithm.

Key words： UAV network； virtual force； network deployment； coverage

1 概述

無人機(jī)網(wǎng)絡(luò)[1]由無人機(jī)（Unmanned Aerial Vehicle，UAV）節(jié)點(diǎn)組成，也可稱為無人機(jī)Ad Hoc網(wǎng)絡(luò)（Unmanned Aerial Vehicle network）。無人機(jī)平臺作為偵察和監(jiān)測的有效手段，很早就被應(yīng)用到在軍事和民用的應(yīng)用中。使用無人機(jī)可以完成一系列復(fù)雜的任務(wù)，如搜索、摧毀，邊境監(jiān)視，林火治理，災(zāi)害監(jiān)測等任務(wù)，并且具有較高的應(yīng)用價值。

但無人機(jī)在提供通信服務(wù)方面一直受到很大限制，尤其當(dāng)多架無人機(jī)通過組網(wǎng)的方式形成通信中繼網(wǎng)絡(luò)時，無人機(jī)節(jié)點(diǎn)的移動性和網(wǎng)絡(luò)拓?fù)涞膭討B(tài)特點(diǎn)會對節(jié)點(diǎn)間的通信質(zhì)量造成沖擊。無人機(jī)網(wǎng)絡(luò)可以作為中繼網(wǎng)絡(luò)[2]使用，如固定網(wǎng)絡(luò)的延伸部分，為無法連接到固定網(wǎng)絡(luò)區(qū)域的用戶提供臨時的通信服務(wù)，同時也可以形成獨(dú)立的網(wǎng)絡(luò)，負(fù)責(zé)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)間的通信，具有較好的實(shí)用性[3]，為了使得無人機(jī)網(wǎng)絡(luò)的通信變得可靠，需要對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行相應(yīng)的控制，以確保網(wǎng)絡(luò)能夠保持較好的網(wǎng)絡(luò)性能。這也是本文的研究方向。

2 無人機(jī)網(wǎng)絡(luò)簡介

Ad Hoc網(wǎng)絡(luò)，又稱無線自組織網(wǎng)絡(luò)，是一種多跳的、無中心的、能夠自組織的網(wǎng)絡(luò)。Ad Hoc是由一組具有無線通信功能的移動終端組成的多跳臨時性自治系統(tǒng)，每個終端都具有平等的地位。各節(jié)點(diǎn)之間的通信通過無線互聯(lián)，通過有效的機(jī)制進(jìn)行網(wǎng)絡(luò)信息的共享，整個過程不需要人為的控制或者中心節(jié)點(diǎn)的調(diào)度。

無人機(jī)網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都具有兩種功能，一種是作為主機(jī)，可以在終端上運(yùn)行各種應(yīng)用程序；一種是作為路由器，可以運(yùn)行相應(yīng)的路由協(xié)議，對數(shù)據(jù)包進(jìn)行處理、轉(zhuǎn)發(fā)。所以無線自組網(wǎng)的這種分布式和無中心的網(wǎng)絡(luò)結(jié)構(gòu)特性使得網(wǎng)絡(luò)在復(fù)雜環(huán)境下能夠維持較好的通信能力，具有很強(qiáng)的抗毀性和魯棒性。由于網(wǎng)絡(luò)中移動節(jié)點(diǎn)都具有路由的功能，可以將網(wǎng)絡(luò)中的節(jié)點(diǎn)通過無線的方式連接成任意的拓?fù)浣Y(jié)構(gòu)。

3 無人機(jī)網(wǎng)絡(luò)的特點(diǎn)

無人機(jī)網(wǎng)絡(luò)是基于無人機(jī)集群構(gòu)建的，充分地利用了無人機(jī)的優(yōu)良特性。相比有人機(jī)，無人機(jī)無論是從飛機(jī)體積、重量還是外形都相對較小，更靈活也更具生命力。同時因?yàn)闊o人機(jī)的造價相比有人機(jī)低廉很多，不害怕?lián)p毀，所以可以同時使用多架無人機(jī)去完成某一特定任務(wù)，這時就需要通過飛行Ad Hoc網(wǎng)絡(luò)來維持無人機(jī)之間的通信[4]。相比常見的固定網(wǎng)絡(luò)、或者無線的蜂窩網(wǎng)絡(luò)，無人機(jī)網(wǎng)絡(luò)具有以下特征：

3.1 拓?fù)浣Y(jié)構(gòu)動態(tài)變化

由于無人機(jī)的移動性、環(huán)境的復(fù)雜性、無線信道之間的干擾等因素，無人機(jī)網(wǎng)絡(luò)處于高度動態(tài)的環(huán)境中，無人機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不斷發(fā)生變化，并且這種變化難以預(yù)測。

3.2 多跳的通信方式

由于無人機(jī)節(jié)點(diǎn)的無線傳輸范圍會有一定的限制，為了能夠?qū)崿F(xiàn)點(diǎn)與點(diǎn)之間的通信或者是進(jìn)行全網(wǎng)廣播或者組播，就要求無人機(jī)網(wǎng)絡(luò)具有多跳轉(zhuǎn)發(fā)的通信機(jī)制，即網(wǎng)絡(luò)中的消息需要經(jīng)過中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)才能完成投遞。

3.3 自組織

無人機(jī)網(wǎng)絡(luò)是由無人機(jī)組成的臨時無線自治系統(tǒng)。由于無人機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會因?yàn)楣?jié)點(diǎn)的移動而發(fā)生改變，所以目前的一些無線路由技術(shù)不能適用。無人機(jī)網(wǎng)絡(luò)應(yīng)具有在無基礎(chǔ)設(shè)施的前提下可以實(shí)現(xiàn)快速的組網(wǎng)的能力。

3.4 網(wǎng)絡(luò)的分布式控制

由于無人機(jī)網(wǎng)絡(luò)中的節(jié)點(diǎn)既是移動終端同時兼有路由的功能，因?yàn)椴淮嬖谥行目刂乒?jié)點(diǎn)，所以每個節(jié)點(diǎn)的地位都是平等的，一般都采用的是分布控制的方式，這樣也增強(qiáng)了網(wǎng)絡(luò)的魯棒性和抗毀性。

4 移動部署算法設(shè)計

4.1 無人機(jī)節(jié)點(diǎn)的運(yùn)動分析

假設(shè)在二維平面內(nèi)，無人機(jī)集群是由N個相同的無人機(jī)組成，分別表示為N1，N2….，Nn。對于單個無人機(jī)節(jié)點(diǎn)，其運(yùn)動服從運(yùn)動學(xué)規(guī)律，可以用數(shù)學(xué)模型表示為：

[xi=vimivi=Fi] （1）

其中，xi，vi，mi，F(xiàn)i分別表示第i個無人機(jī)的位置向量、速度向量、節(jié)點(diǎn)質(zhì)量和控制輸入量。

在本文中，節(jié)點(diǎn)通過迭代計算的方式更新本地的運(yùn)動狀態(tài)信息并計算目標(biāo)位置，令Xi表示單個節(jié)點(diǎn)的運(yùn)動狀態(tài)量：

[Xik=xikvik] （2）

Xi（k）表示節(jié)點(diǎn)i在k時刻的運(yùn)動狀態(tài)，xi（k）表示其位置向量，vi（k）表示其速度向量。將公式3進(jìn)行離散化得到節(jié)點(diǎn)狀態(tài)量的迭代計算公式：

[Xik+1=1T01xikvik+tT-t2tFikmi] （3）

其中T為每一步的時間長度，F(xiàn)i（k）為k時刻節(jié)點(diǎn)i的控制輸入，t表示控制輸入的作用時間。通過公式3-16就可以由當(dāng)前的運(yùn)動狀態(tài)信息計算得到下一時刻的運(yùn)動狀態(tài)。根據(jù)該運(yùn)動狀態(tài)更新方程可知，在每一個時隙T內(nèi)節(jié)點(diǎn)會先做t秒的勻加速運(yùn)動，當(dāng)速度達(dá)到某節(jié)點(diǎn)的速度上限時，節(jié)點(diǎn)停止加速運(yùn)動并在剩余的時間做勻速直線運(yùn)動，直到該輪移動過程結(jié)束。

因?yàn)楸疚闹胁捎玫氖欠植际降姆椒ㄟM(jìn)行移動部署，每個節(jié)點(diǎn)可以進(jìn)行自主的移動。節(jié)點(diǎn)能夠獲得鄰居節(jié)點(diǎn)的相關(guān)信息，并根據(jù)移動算法進(jìn)行移動，移動部署算法的具體內(nèi)容如表1所示。

表1 單興趣點(diǎn)覆蓋移動部署算法

[初始化：

初始化節(jié)點(diǎn)、興趣點(diǎn)的初始位置，并將初始化為0；

節(jié)點(diǎn)通過廣播消息將自己的相關(guān)信息發(fā)送給一跳鄰居；＼&本地信息更新：

While（True）do{

節(jié)點(diǎn)i在T的時間內(nèi)接收一跳鄰居發(fā)送的廣播包，并根據(jù)廣播包內(nèi)的信息更新本地信息：

1）節(jié)點(diǎn)通過收到的Hello消息生成一個鄰居表Ni，Ni中記錄了節(jié)點(diǎn)i的一跳鄰居；

2）當(dāng)節(jié)點(diǎn)i的flag值為0時，節(jié)點(diǎn)i判斷興趣點(diǎn)是否在自己的通信范圍內(nèi)，如果是，再判斷自己的鄰居節(jié)點(diǎn)中，是否有節(jié)點(diǎn)的flag值為1，如果沒有就將自己的flag值設(shè)為1；反之如果有就將自己的flag值設(shè)為2；

3）當(dāng)興趣點(diǎn)沒有在節(jié)點(diǎn)的通信范圍內(nèi)時，就判斷自己的鄰居節(jié)點(diǎn)中是否有節(jié)點(diǎn)的flag值非零，如果有，當(dāng)節(jié)點(diǎn)i的鄰居個數(shù)大于2時，就將自己的flag值設(shè)為2；

4）當(dāng)節(jié)點(diǎn)沒有鄰居且flag值非0時，將flag置0；

}＼&主要步驟：

While（||vi||>vth） do {

節(jié)點(diǎn)i的速度大于閾值時，節(jié)點(diǎn)計算所受的虛擬力：

1）判斷節(jié)點(diǎn)所受虛擬力的類型：

[if flagi==2 Fi′=j∈NFij； Fi=Fi′+Fiv；else Fi′=j∈NFij+FiP； Fi=Fi′+Fiv； ]

2）判斷虛擬力作用的時間：

[if Fi′miT>vmax t=vmaxFi′T；else t=T； ]

3）計算虛擬力并更新運(yùn)動狀態(tài)：

[xi=xi+viT+tT-t2Fi2mi ；vi=vi+Fitmi； ]

4）節(jié)點(diǎn)會根據(jù)計算所得的虛擬力移動到下一目的位置，并通過Hello消息將自己的信息廣播給自己的一跳鄰居。

}＼&]

5 實(shí)驗(yàn)仿真

本文基于MATLAB2013b軟件對提出的算法進(jìn)行仿真，仿真的區(qū)域?yàn)?00m×500m的正方形區(qū)域，實(shí)驗(yàn)中節(jié)點(diǎn)的個數(shù)從10變化到100，節(jié)點(diǎn)通信半徑的變化范圍為10m到100m，目的是測試不同條件下算法的性能。在整個部署過程中，每一輪的時間間隙為T=1秒。速度閾值vth=0.1m/s，當(dāng)所有節(jié)點(diǎn)的速度小于這一閾值時，認(rèn)為網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)近似達(dá)到一種穩(wěn)定狀態(tài)。節(jié)點(diǎn)的初始部署狀態(tài)是隨機(jī)分布在整個指定區(qū)域內(nèi)，具體的實(shí)驗(yàn)參數(shù)如表2中所示。

表2 實(shí)驗(yàn)參數(shù)

[區(qū)域大?。?amp;500m×500m＼&節(jié)點(diǎn)個數(shù)＼&10～100＼&通信半徑Rc＼&10m～100m＼&最優(yōu)距離dopt＼&Rc-0.5＼&時間步長T＼&1s＼&速度閾值vth＼&0.1m/s＼&興趣點(diǎn)的位置＼&（0，0）＼&K1＼&0.25＼&K2＼&-0.25＼&K3＼&-1/t＼&]

5.1 拓?fù)渥兓?/p>

圖1中所示為本文算法中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨著時間的變化，選取的最大速度為5m/s，節(jié)點(diǎn)個數(shù)為50，通信半徑為30m。初始時，網(wǎng)絡(luò)中的節(jié)點(diǎn)隨機(jī)的分布在整個區(qū)域內(nèi)，如圖1（a）所示。

圖1 場景一拓?fù)渥兓?/p>

此后所有節(jié)點(diǎn)逐漸向興趣點(diǎn)移動，并在興趣點(diǎn)周圍形成一個連通的網(wǎng)絡(luò)，如圖1（b）（c）。當(dāng)興趣點(diǎn)對所有節(jié)點(diǎn)不再產(chǎn)生力的作用時，節(jié)點(diǎn)只受到節(jié)點(diǎn)間作用力和速度反饋控制力的影響，并在此基礎(chǔ)上進(jìn)一步調(diào)整網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖1（e）所示?？梢钥吹綀D1（e）（f）中，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)基本保持穩(wěn)定，類似正三角形拓?fù)浣Y(jié)構(gòu)，滿足拓?fù)淇刂频哪繕?biāo)。

5.2 覆蓋范圍

圖2中為網(wǎng)絡(luò)的覆蓋范圍與節(jié)點(diǎn)通信半徑之間的關(guān)系，節(jié)點(diǎn)個數(shù)為50，通信半徑從10m變化到100m。因?yàn)橥ㄟ^幾何方法計算網(wǎng)絡(luò)的通信覆蓋范圍較為困難，所以本文采用蒙特卡洛的方法來評估網(wǎng)絡(luò)的覆蓋范圍。在給定的區(qū)域內(nèi)均勻部署2.5×105個點(diǎn)，并檢測這些點(diǎn)中一共有多少點(diǎn)能夠被無人機(jī)節(jié)點(diǎn)所覆蓋，并用被覆蓋點(diǎn)占所有點(diǎn)的比例代替網(wǎng)絡(luò)的覆蓋范圍。下文中關(guān)于覆蓋范圍的實(shí)驗(yàn)均以該種方式計算實(shí)驗(yàn)結(jié)果。網(wǎng)絡(luò)的覆蓋范圍的大小可表示為：

[＼&（4）＼&]

由公式4可知，網(wǎng)絡(luò)覆蓋范圍的大小與通信半徑的平方成正比。隨著通信半徑的增加，覆蓋范圍不斷增大。由于覆蓋區(qū)域有限，當(dāng)半徑較大時，有些節(jié)點(diǎn)會覆蓋到區(qū)域以外的地方，這一部分的面積不計算在內(nèi)，所以可以看到兩種算法在通信半徑為100m時的覆蓋范圍接近1，表明指定的區(qū)域都基本被覆蓋。從圖2中可以看出，兩種算法的覆蓋范圍隨著通信半徑的增大都是逐漸增大，并最后趨近概率1。但在通信半徑較大時，文獻(xiàn)[5]算法的覆蓋范圍小于本文算法的覆蓋范圍。本文算法中針對不同的最大速度，分別選擇0.5m/s、1m/s、5m/s、10m/s四種速度上限，可以看到對于不同的最大速度其最后的覆蓋范圍基本相同。

圖2 覆蓋范圍隨通信半徑變化

5.3 連通性

圖3 連通概率隨通信半徑變化

圖3中所示為網(wǎng)絡(luò)連通概率隨通信半徑的變化曲線，分別選擇節(jié)點(diǎn)個數(shù)為50個和30個兩種情況進(jìn)行分析，本文算法的最大速度分別選擇的是0.5m/s和5m/s。從圖中可知當(dāng)本文算法選擇不同的最大速度時，最終形成的網(wǎng)絡(luò)在不同的通信半徑下都能保持1或近似1的連通概率。文獻(xiàn)[5]算法無法在半徑較小時維持較好的連通性，這與其在半徑較小時具有較大的節(jié)點(diǎn)間斥力和較小的興趣點(diǎn)引力有關(guān)。

6 結(jié)論

本文針對無人機(jī)的運(yùn)動特性，提出了一種速度可控的虛擬力模型，并將該模型看作控制目標(biāo)，推導(dǎo)出節(jié)點(diǎn)受力的微分方程?？梢钥闯龉?jié)點(diǎn)的受力與節(jié)點(diǎn)位置信息和速度信息相關(guān)，模型較為簡單，并能夠準(zhǔn)確描述節(jié)點(diǎn)在真實(shí)環(huán)境中的運(yùn)動特征。本文中結(jié)合節(jié)點(diǎn)移動受控特性，引入了速度反饋?zhàn)饔昧ΓO(shè)計了一種自主的移動部署方法則是研究如何能夠通過節(jié)點(diǎn)的自主移動部署改善網(wǎng)絡(luò)的性能，即利用節(jié)點(diǎn)的移動性對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行重構(gòu)，使得網(wǎng)絡(luò)的相關(guān)性能，如連通性、覆蓋范圍、移動代價等指標(biāo)達(dá)到設(shè)計要求。

參考文獻(xiàn)：

[1] Bekmezci I， Sahingoz O K， Temel ?. Flying ad-hoc networks （FANETs）： a survey[J].Ad Hoc Networks， 2013，11（3）： 1254-1270.

[2] Pignaton de FreitasE. UAV relay network to support WSN connectivity. in Ultra Modern Telecommunications and Control Systems and Workshops （ICUMT） [J].2010 International Congress on， 2010.

[3] Chlamtac I， Conti M， Liu J J N.Mobile ad hoc networking： imperatives and challenges[J].Ad Hoc Networks， 2003， 1（1）： 13-64.

[4] 毛鶯池.與位置無關(guān)的無線傳感器網(wǎng)絡(luò)連通性覆蓋協(xié)議[J].軟件學(xué)報， 2007， 18（7）： 1672-1684.

[5] Liu H. Simple movement control algorithm for bi-connectivity in robotic sensor networks. Selected Areas in Communications[J].IEEE Journal on， 2010，28（7）： 994-1005.