劉 暢，杜文才，任 佳

(海南大學 信息科學技術(shù)學院，海南 ?？?570228)

基于定向天線的無人船編隊拓撲控制算法

劉 暢，杜文才，任 佳

(海南大學 信息科學技術(shù)學院，海南 ?？?570228)

為了解決無人船編隊組網(wǎng)時定向天線的方向性制約問題，提出了一種基于定向天線的分布式拓撲控制算法，通過調(diào)整網(wǎng)絡中各個節(jié)點的發(fā)射功率來實現(xiàn)全網(wǎng)絡快速連通.仿真實驗證明，該算法能夠以較低能耗代價維護網(wǎng)絡的連通性能.

定向天線； 無人船； 節(jié)能； 拓撲控制

多無人船編隊在海上航行使用全向天線進行信號傳輸.全向天線在信號傳輸可靠性能方面表現(xiàn)優(yōu)異，全面覆蓋360°的范圍，信號所覆蓋的區(qū)域可以簡化為圓形，沒有死角，但是全向天線的增益較小，傳輸半徑受限，能量消耗較高.定向天線與全向天線相比較，負責一定角度范圍的信號傳輸，優(yōu)點是能量聚集，增益較高，缺點是定向天線模型所構(gòu)建出的網(wǎng)絡拓撲則會使信號覆蓋區(qū)域更加復雜且不規(guī)則.

現(xiàn)有的拓撲控制算法主要分為集中式拓撲控制和分布式拓撲控制.集中式控制算法需要全網(wǎng)絡的拓撲信息，在海面應用環(huán)境下難以適應無人船編隊的網(wǎng)絡拓撲稀疏性特征.分布式控制算法可通過相鄰無人船交互的GPS信息，獲得彼此的位置信息，完成無人船編隊局部網(wǎng)絡拓撲控制.

文獻[1]通過構(gòu)造有序的鄰跳節(jié)點集合來約束每個節(jié)點的最大發(fā)射功率，以實現(xiàn)容錯性能較優(yōu)的分布式拓撲；文獻[2]通過調(diào)整節(jié)點發(fā)射功率，改變其配置的天線波束的朝向、寬度和增益形成拓撲；文獻[3]提出異構(gòu)無線自組網(wǎng)拓撲控制算法K-DRNG，解決了無線自組網(wǎng)中節(jié)點異構(gòu)、帶寬受限等問題.上述算法都未考慮網(wǎng)絡拓撲控制的能量消耗問題，尤其是在無人船自帶能源有限和海上補給困難等因素的制約下，如何有效降低無人船節(jié)點拓撲控制的能量消耗成為無人船編隊組網(wǎng)需要解決的首要問題.

針對該問題，筆者提出基于定向天線的無人船拓撲控制算法(Directional Antenna-based Unmanned-ship Topology Control, DAUTC)，實現(xiàn)了無人船節(jié)點發(fā)射功率的自適應調(diào)整，保證海上無人船編隊網(wǎng)絡稀疏拓撲結(jié)構(gòu)的連通性.DAUTC算法通過控制節(jié)點的發(fā)射功率達到對拓撲結(jié)構(gòu)進行控制的目的，在發(fā)送方和接收方參數(shù)及信道參數(shù)固定在理想狀態(tài)下，采用收集局部鄰跳節(jié)點所在扇區(qū)位置物理信息方法，解決網(wǎng)絡動態(tài)變化所帶來的到達角度無法測量的問題.當節(jié)點的分布更為密集以及傳輸環(huán)境變得越來越復雜時，可以通過改變信道增益以及使用低功率發(fā)射信號以節(jié)省通信功率，簡化整個網(wǎng)絡的拓撲結(jié)構(gòu)，使節(jié)點信號順利通過信道，減少不必要的碰撞，能夠極大改善網(wǎng)絡的連通性能.

1 基于定向天線的無人船拓撲控制算法(DAUTC)

1.1 DAUTC算法組成 節(jié)點的能耗優(yōu)劣與發(fā)射功率之間的關(guān)系依賴于節(jié)點搭載的定向天線信號有效覆蓋半徑，即發(fā)射信號的有效覆蓋半徑的長度越短，整個節(jié)點能耗越低.多無人船網(wǎng)絡拓撲具有實時動態(tài)變化的特性，其特征主要體現(xiàn)在鏈路連通性，時延性，網(wǎng)絡吞吐量等性質(zhì).因此，要求設計的拓撲控制算法在拓撲結(jié)構(gòu)發(fā)生動態(tài)改變時充分評估上述影響因素，能夠快速構(gòu)成新的全連通網(wǎng)絡并以較小的能量消耗維護網(wǎng)絡特性.為此，筆者提出DAUTC算法.

DAUTC算法主要分為2個階段：信息采集以及拓撲控制.

2) 在拓撲控制階段，每個節(jié)點具有唯一可識別的ID號碼，每個無人船節(jié)點b都配備有N個自帶扇區(qū)信息的定向天線，φ表示信號發(fā)射朝向，該方向可由節(jié)點控制且節(jié)點b的發(fā)射功率可以在自身的范圍內(nèi)連續(xù)的調(diào)節(jié)，即有0≤Pb≤Pbmax，Pbmax即節(jié)點b的最大發(fā)射功率.在由所有無人船組節(jié)點所形成的自組拓撲網(wǎng)絡中，每個節(jié)點具有相同的最大發(fā)射功率均為Pmax.節(jié)點同時有配備GPS，以便得知位置信息.假設節(jié)點之間的傳輸具有相同且對稱的路徑損耗，發(fā)射天線與接收天線之間的信號傳輸功率按照不同距離發(fā)生η次衰減.由此可得，以dis(b,c)為距離的節(jié)點b與c所需要的最小功率為P(b,c)=tdis(b,c)η.

在雙徑模型中，此時η=4，則發(fā)射功率Pt與接收功率Pr有如下關(guān)系

(2)

其中，ht是發(fā)射天線高度，hr是接收天線的高度.當傳輸介質(zhì)假設為(均勻且對稱)，則P(b,c)=P(c,b)，向信號所覆蓋的扇區(qū)內(nèi)的節(jié)點發(fā)送信號.

1.2DAUTC算法及其優(yōu)化算法DAUTC算法具體流程

步驟1 為節(jié)點b設置初始發(fā)射功率Pb，將覆蓋有N個扇區(qū)的節(jié)點b設置其為空白扇區(qū)(即所覆蓋區(qū)域沒有b的鄰跳節(jié)點)；

步驟2 通過調(diào)節(jié)，逐漸增大節(jié)點b的發(fā)射功率，并向各個空白扇區(qū)發(fā)送“Hi”信息包，然后逐一收集來自其他節(jié)點的“Back”信息包，里面含有其他節(jié)點的扇區(qū)位置信息；若節(jié)點b發(fā)現(xiàn)新的節(jié)點c，則節(jié)點b將節(jié)點c及其信息收入本地鄰跳節(jié)點集合I(b)中，并改變節(jié)點b負責該扇區(qū)的天線屬性，標記為非空扇區(qū)；

介紹了歷史上最特別的照片背后的故事。這些照片以一種奇怪而強大的方式塑造了我們看待世界的方式，影響著我們對現(xiàn)實的看法。

步驟3 節(jié)點b通過篩選，得到連結(jié)I(b)內(nèi)全部節(jié)點所必要的最小發(fā)射功率的最大值，將其設置為節(jié)點b的發(fā)射功率，并以此功率發(fā)射信號，算法結(jié)束.

步驟4 重復以上步驟，直到節(jié)點b的發(fā)射功率Pb=Pbmax，或節(jié)點b的天線覆蓋范圍內(nèi)無空白扇區(qū)為止.

使用DAUTC算法處理后，無人船組所形成的網(wǎng)絡拓撲結(jié)構(gòu)并不是一個平坦均勻的拓撲圖.為了使拓撲結(jié)構(gòu)簡化，信道中各個節(jié)點的碰撞減少，節(jié)點度數(shù)降低，網(wǎng)絡吞吐量提高等，在DAUTC算法得到的拓撲圖上進行優(yōu)化處理算法，更進一步對拓撲圖中多余的單向邊帶進行刪除，最終可以得到稀疏平坦的拓撲結(jié)構(gòu).

DAUTC優(yōu)化算法具體流程

步驟1 網(wǎng)絡中所有存在的節(jié)點均向外發(fā)射其扇區(qū)位置信息，同時接收來自其鄰跳節(jié)點的扇區(qū)位置信息；

步驟2 節(jié)點b收集其鄰跳節(jié)點集合I(b)中全部節(jié)點的扇區(qū)位置信息；

步驟5 當節(jié)點b收到c發(fā)出的消息acc(b,c)以后，保留圖Pic中的雙向邊；

步驟6 重復以上步驟，使每個節(jié)點對其他任意節(jié)點都能夠遍歷.

2 算法的性能仿真

為了驗證DAUTC算法以及DAUTC優(yōu)化算法的有效性能，通過分析在不同的業(yè)務量負載下，不同的網(wǎng)絡拓撲結(jié)構(gòu)中，比較2種算法所的到的拓撲結(jié)構(gòu)端到端傳輸量、平均節(jié)點度以及最大節(jié)點度等指標，得到算法的優(yōu)劣情況.

2.1 仿真條件 設置仿真實驗條件時，將無人船節(jié)點隨機均勻分布在一個1 000×1 000m2的海域之間，各個無人船節(jié)點的最大傳輸半徑是100m，節(jié)點數(shù)設置為50～100個.在仿真中，考慮到無人船自身的結(jié)構(gòu)尺寸，令其安全距離為5m.在每個無人船節(jié)點上安放N=8扇區(qū)數(shù)的定向天線，即π/4的弧度的范圍由一個扇區(qū)覆蓋，選用算法中的雙徑模型，該模型的衰減系數(shù)η=4，初始時，令發(fā)射天線的信號增益為0dB，接收天線的信號增益為0dB.

為了能夠得到在不同拓撲結(jié)構(gòu)下的網(wǎng)絡在加載業(yè)務后的性能分析結(jié)果，采用Matlab仿真軟件進行實驗測試，各個網(wǎng)絡節(jié)點的運動場景設置如下：取100個節(jié)點，將其隨機分布在一個1 000×1 000m2的海域之中，各個節(jié)點在數(shù)據(jù)鏈路層采用基于802.11無線局域網(wǎng)協(xié)議，MAC層采用了CSMA/CA多址接口接入方式，仿真時間為600s，共統(tǒng)計10次.

2.2 拓撲結(jié)構(gòu)在網(wǎng)絡中的性能對比 節(jié)點度是評判無線網(wǎng)絡結(jié)構(gòu)性能優(yōu)劣的關(guān)鍵衡量指標，而無線網(wǎng)絡拓撲結(jié)構(gòu)性能的優(yōu)劣直接反映了拓撲結(jié)構(gòu)控制算法的性能優(yōu)劣.在無線路由協(xié)議中，各個節(jié)點均期望與有限個數(shù)鄰節(jié)點發(fā)生通信，節(jié)點度越大，則會增加其他節(jié)點對該節(jié)點及鄰節(jié)點的干擾，增加了維護相互鄰跳狀態(tài)的能耗.在仿真實驗中，選取與節(jié)點度數(shù)有關(guān)的最大節(jié)點度和平均節(jié)點度2個指標，來驗證DAUTC及其優(yōu)化算法的有效性.

圖3 未拓撲控制 圖4DAUTC算法 圖5DAUTC優(yōu)化算法

當節(jié)點數(shù)為100個時，未經(jīng)過拓撲控制的拓撲結(jié)構(gòu)如圖3所示.此時，每個節(jié)點都以最大功率進行通信，保證在信號傳輸范圍內(nèi)能夠接收到所有鄰跳節(jié)點的信息，傳輸半徑保持在100m.不同的拓撲控制算法所形成的拓撲結(jié)構(gòu)如圖4和5所示.圖4是經(jīng)過DAUTC算法后得到的網(wǎng)絡拓撲圖，相比于圖3，已經(jīng)有很明顯的網(wǎng)絡稀疏性；圖5是經(jīng)過DAUTC優(yōu)化算法得到的網(wǎng)絡拓撲圖，平均節(jié)點度顯著降低.從3幅圖可以清楚觀察到，經(jīng)過優(yōu)化算法所導出的網(wǎng)絡拓撲結(jié)構(gòu)更為簡單平整，平均節(jié)點度更小，功率有效性更高.

圖6和圖7中分別反映了各個算法形成的平均節(jié)點度和最大節(jié)點度.獲得優(yōu)化后的拓撲圖，節(jié)點密度都相對比較穩(wěn)定，均保持在3個以內(nèi)，并且最大節(jié)點數(shù)都在8個以內(nèi).圖6顯示了不同的拓撲算法獲得的網(wǎng)絡拓撲的平均節(jié)點度，節(jié)點度若是小，則有利于信道的空間利用率.當整個網(wǎng)絡不采用拓撲控制算法的時候，隨著節(jié)點數(shù)量快速增長，節(jié)點度則快速增加；DAUTC算法導出的網(wǎng)絡拓撲結(jié)構(gòu)會隨著節(jié)點密度增大、節(jié)點度增加而表現(xiàn)出更為緩慢的增加趨勢；DAUTC優(yōu)化算法形成的拓撲結(jié)構(gòu)的節(jié)點度則隨著節(jié)點數(shù)的增加而保持基本不變.

通過仿真可得，通過DAUTC算法及其優(yōu)化算法所確定的節(jié)點平均傳輸半徑較小，既保證了網(wǎng)絡連通性，又保證了節(jié)點的節(jié)能性，并簡化了整個網(wǎng)絡的復雜度，大大延長了網(wǎng)絡壽命.通過多次仿真實驗可得，與使用最大功率發(fā)射信號相比而言，通過降低節(jié)點的發(fā)射功率，建立更為簡單的連通網(wǎng)絡，提高了帶寬的重復利用率以及網(wǎng)絡的吞吐量.

3 小 結(jié)

隨著定向天線技術(shù)的智能化發(fā)展，根據(jù)天線的特性可通過調(diào)節(jié)網(wǎng)絡中各個節(jié)點的發(fā)射功率對海上航行的多無人船組全網(wǎng)絡的拓撲結(jié)構(gòu)進行控制，并能夠顯著提高通信質(zhì)量.在無人船組中，使用定向天線保證以最優(yōu)節(jié)能的功率實現(xiàn)網(wǎng)絡連通，最終形成稀疏的平坦網(wǎng)絡結(jié)構(gòu).因為各個節(jié)點是以較低功率發(fā)射并且由算法形成的拓撲圖中平均節(jié)點數(shù)最小，所以網(wǎng)絡性能在節(jié)能性方面得到了優(yōu)化.使用DAUTC算法，可以保證整個網(wǎng)絡的連通率大于95%，可使平均節(jié)點度和最大節(jié)點度降低，并保證節(jié)點的傳輸半徑比初始半徑小，降低能耗，提高了該網(wǎng)絡的能量有效性.采用更為有效的拓撲控制算法后，可以獲得優(yōu)于全向天線的拓撲結(jié)構(gòu)，提高了能量效率.

[1] 劉興川, 吳振鋒, 趙克儉. 異構(gòu)多跳無線傳感器網(wǎng)絡容錯性拓撲控制算法[J]. 系統(tǒng)工程與電子技術(shù), 2015, 37(8):1 902-1 908.

[2] 王東, 陳文斌, 李曉鴻,等. 自組網(wǎng)中基于自適應波束天線的拓撲控制算法[J]. 計算機研究與發(fā)展, 2010, 47(3):407-415.

[3] 劉軍, 孫茜, 李少華,等. 基于定向天線的無線自組網(wǎng)拓撲控制算法[J]. 東北大學學報：自然科學版, 2012, 33(9):1 257-1 260.

[4] 周衛(wèi), 董榮勝.AdHoc局部網(wǎng)絡拓撲信息對能量有效拓撲控制的影響[J]. 桂林電子科技大學學報, 2012, 32(6):442-446.

[5] 李小龍, 馮東磊, 彭鵬程. 一種基于勢博弈的無線傳感器網(wǎng)絡拓撲控制算法[J]. 物理學報, 2016, 65(2):342-351.

[6] 賀鵬, 李建東, 陳彥輝,等.AdHoc網(wǎng)絡中基于方向性天線的分布式拓撲控制算法[J]. 軟件學報, 2007, 18(6):1 308-1 318.

[7] 王飛. 無線傳感網(wǎng)中基于梯度的能量感知分簇拓撲算法研究[D].鄭州：鄭州大學, 2015.

[8] 江禹生, 李萍, 馬超. 一種能量高效的無線傳感器網(wǎng)絡拓撲控制算法[J]. 傳感器與微系統(tǒng), 2014, 33(2):146-149.

[9] 周志前. 基于遺傳策略的無線傳感器網(wǎng)絡拓撲控制研究[D].長沙：長沙理工大學, 2014.

[10] 韓志杰, 黃劉生, 王汝傳,等. 一種基于位置和拓撲控制的無線傳感器網(wǎng)絡路由算法[J]. 計算機研究與發(fā)展, 2010, 47(s2):128-132.

[11] 劉浩然, 韓濤, 李雅倩,等. 具有路徑能耗優(yōu)化特性的WSN無標度容錯拓撲控制算法[J]. 通信學報, 2014, 35(6):64-72.

Topology Control Algorithm of Unmanned Aerial Vehicle Formation Based on Directional Antenna

Liu Chang, Du Wencai, Ren Jia

(College of Information Sciences and Technology, Hainan University, Haikou 570228, China)

Under the same power consumption condition, the directional antenna can generate higher gain and provide a larger transmission range, and which are suitable for unmanned ship formation under marine environment. In order to solve the direction control problem of directional antenna when the networks among the UAV formation are created, a distributed topology control algorithm based on directional antenna was proposed. By adjusting the transmitting power of each node in the network, the fast connectivity of the network was accomplished. Simulation results showed that the proposed algorithm can maintain the connectivity of the network at a lower cost.

directional antenna; unmanned ship; energy saving; topology control

2016-12-30

國家國際科技合作專項(2015DFR10510)，海南省重點實驗室和工程技術(shù)研究中心建設專項(gczx2014004)，海南省自然科學基金(20166209)

劉暢(1990-)，女，河南新鄉(xiāng)人，海南大學2014級碩士研究生，研究方向：海洋通信，E-mail:282956820@qq.com

杜文才(1953-)，男，江蘇徐州人，博士，教授，博士生導師，研究方向：海洋通信，E-mail:13086000882@163.com

1004-1729(2017)02-0106-05

TP 181

A DOl：10.15886/j.cnki.hdxbzkb.2017.0019