a Communication and Network基于ADS-B報文的航空自組網(wǎng)分簇算法張海',李綱,陳廣曉2,李靜林2(1.空軍裝備研究院雷達與電子對抗研究所,北京100876;2.北京郵電大學網(wǎng)絡與交換技術國家重點實驗室,北京100876)摘要∶在大規(guī)模Ad-loc網(wǎng)絡中,有效的層次架構是實現(xiàn)路由和資源管理的關鍵技術。針對航空網(wǎng)絡中因飛機數(shù)量增加、網(wǎng)絡規(guī)模増大而導致網(wǎng)絡中飛機通信質(zhì)量下降的問題,提出了一種基于ADS-B報文的航空Ad-Hoc網(wǎng)絡分簇算法。該算法利用ADS-B報文提供的飛機速度、位置信息、連同節(jié)點度,進行簇的形成和維護。設計了大量的仿真實驗,結果表明該算法可以減少簇的個數(shù)和節(jié)點切換率,從而有效提高了簇的穩(wěn)定性和航空通信的效率。關鍵詞:航空電信網(wǎng);ADS-B;Ad-Hoc;分簇算法中圖分類號:TM929.5文獻標識碼:A文章編號:0258-7998(2013)07-0089-04An ADS-B based clustering algorithm in aviation Ad-Hoc networksLi jinglin(1. Radar and EW Institute, Equipment Academy of Air Force, Beijing 100876,China2. Beijing University of Posts and Telecommunications, State Key Laboratory of Networking andSwitching Technology, Beijing 100876, ChinaAbstract: An effective architecture is the key technology of routing and resource managing in large Ad-Hoc networks. In theaviation network, the quality of communication between aircrafts declines with the increasing number of aircrafts.Todeal with thisproblem, an ADS-B message based novel clustering algorithm is presented for aviation Ad-Hoc networks. The piuses the mobility and location of aircraft, provided by ADS-B messages and node degree for cluster formation and maintenanceSome simulations are performed and the results indicate that the proposed algorithm can lower the number of clusters and the rateof switching nodes, and it can effectively improve the cluster stability and efficiency of aeronautical communicationsKey words: aeronautical telecommunication network: ADS-B: Ad-Hoc: clusterADS-B技術是未來航空監(jiān)視的主要手段之一,它點競爭有限的無線信道,增加了發(fā)生碰撞的概率。為減以地空/空空數(shù)據(jù)鏈為通信手段,以導航系統(tǒng)及其他機少共享相冋信道的節(jié)點數(shù)目、降低碰撞概率、提高信道載設備產(chǎn)生的信息為數(shù)據(jù)源,由具有ADS-B功能的飛利用率須對移動節(jié)點進行分簇14,以提高通信質(zhì)量。機將自身的位置、速度等SV( State Vector)信息周期性對本文提出了一種基于ADS-B報文,綜合移動性、位外廣播,地面站和其他飛機接收這些報文,進行飛機間置、節(jié)點度特點,采用權值進行評估的分簇算法的通信和監(jiān)控。圖1為航空Ad-Hoc網(wǎng),簇內(nèi)飛機可直接通信,簇間隨著飛機性能和數(shù)量的提高,ADS-B應用不斷升級,飛機通過網(wǎng)關通信,相隔太遠的簇對其覆蓋范圍有了更高要求。移動自組網(wǎng)(Ad-Hoc)技術能通信,為增強信道利用率,通過簇頭將信息轉(zhuǎn)發(fā)給基站有效解決這一問題。Ad-Hoc是一種自組織的無線多跳網(wǎng),1傳統(tǒng)分簇算法組網(wǎng)無需固定路由器,所有節(jié)點均移動,并能以任意方式目前存在很多分簇算法,算法直接影響簇的穩(wěn)定動態(tài)地與其他節(jié)點保持聯(lián)系。在航空Ad-Hoc網(wǎng)絡中,由性、大小以及節(jié)點擔任簇頭的時間,從而影響生成簇和于數(shù)據(jù)鏈覆蓋范圍有限導致兩個無法通信的飛機可借助維護簇所需開銷12-51。其他節(jié)點轉(zhuǎn)發(fā)進行通信,擴大了ADS-B的覆蓋范圍最大連接度算法1盡可能減少了路由器的數(shù)目。其由于Ad-Hoc采用共享無線信道方式工作,過多節(jié)思想是,節(jié)點間通過交換控制信息得到鄰居節(jié)點的數(shù)《電子技術應用》2013年第39卷第7期通信與網(wǎng)絡Communication and NetworkO簇成員關系。此時,已在一個簇中的節(jié)點可能離開所在的簇加簇頭入別的簇,而簇頭可能進入別的簇頭的范圍或被毀,簇⊙網(wǎng)關節(jié)點維護是對初始簇形成后上述事件的補救。下面將描述所提出的成簇算法,包括成簇采用的度1簇范圍量、成簇算法和簇維護。2.1簇的度量權值 weight的定義分簇算法要求簇能很好地適應網(wǎng)絡拓撲的動態(tài)變化,在航空網(wǎng)絡中,由于飛機高速移動,移動方向不定08地選擇族頭防止選擇邊緣節(jié)點作為族頭造成的不穩(wěn)飛機的移動性對簇的穩(wěn)定性有很大影響。同時位置信息反映鄰居節(jié)點間的距離,通過位置信息和節(jié)點度能很好定。因此,本文提出一種基于多種因素的權值計算方法,權值為weight=axk x mobility +6 xwxdegree+cxrxdistance (1)圖1航空Ad-Hoc網(wǎng)其中,a,b,c是權值因子,a+b+c=1,據(jù)不同應用場景,設目,該節(jié)點和其鄰居節(jié)點中具有最大度的被選為簇頭,置3個因子的值;k,,r是常數(shù)因子,需保證3個影響因度數(shù)相同時,選D最小的作為簇頭,簇頭的一跳鄰居節(jié)素最后計算時在同一量級上,提高wit精度點為該簇普通成員。其優(yōu)點是簇數(shù)目較少,減少分組投mobility為飛機相對移動性度量,節(jié)點從ADs-B報遞時延,但信道空間重用率較低。文中提取速度和位置信息,采用LET計算兩節(jié)點的相最低移動性算法2-3盡量保持了簇結構的穩(wěn)定性,其對移動性思想是節(jié)點的移動性越高,其權重越低,選最高權重的LET=-(ab+cd)+va+e2)r-(ad-bc 2(2)節(jié)點作為簇頭。該算法需要一種機制來量化節(jié)點的移動性,簡單的方法是通過節(jié)點間相對速度絕對值的時間平a=vcos -v cos0均來衡量節(jié)點的相對移動性?；诘乩砦恢玫乃惴?-是按地理區(qū)域劃分簇結構,c=vine -v sino使地理位置上較靠近的節(jié)點組成簇。其思想是節(jié)點通過交互位置信息確定本地的網(wǎng)絡拓撲,然后依據(jù)鄰居節(jié)點其中是兩個節(jié)點,為其傳輸范圍,速度為v和n,的分布來選擇簇頭并形成簇。此方法可減少簇頭和簇內(nèi)方向角為θ和θ,坐標為(x,y)和(x,y)。通過LET計算兩節(jié)點間通信的總功率和平均傳輸時延,但并非所有節(jié)點節(jié)點間鏈路的持續(xù)時間,反映兩節(jié)點的相對移動性,間都可獲得節(jié)點位置信息。接反映兩節(jié)點相對速度,如:兩節(jié)點距離很近,但相對速以上算法往往只考慮系統(tǒng)中節(jié)點的某一特性,應用度很小,ET會很大;反之,兩節(jié)點距離很遠,但相對速場合受限,簇的性能較差。由于飛機高速移動和方向不度很大,LET會很小。因此,LET越大,說明兩節(jié)點的相定,不能只考慮某一因素。飛機周期性發(fā)送ADS-B報文對移動性很小;反之則說明兩節(jié)點的相對移動性很大。設其攜帶飛機SV信息,因此,本文提出一種基于ADS- B mobil" LEr°報文的分簇算法,將以上幾種傳統(tǒng)算法進行加權來進行成簇和簇維護。為節(jié)點的節(jié)點度與理想度間差值的絕對值2基于ADS-B報文的分簇算法即 Degree=ld-Dl,d和Dd分別為節(jié)點的當前節(jié)點度在成簇算法中,由于網(wǎng)絡拓撲動態(tài)變化1,需維護節(jié)和理想節(jié)點度,選擇理想節(jié)點度的目的是保持簇大小平衡。由于飛機廣播的ADS-B報文只能被傳輸范圍內(nèi)的點的角色信息,如:簇頭、簇成員、孤兒和NUIL。簇成員是簇的基本節(jié)點,實現(xiàn)簇內(nèi)節(jié)點的基本通信,屬于不同跳鄰居節(jié)點接收到,因此,形成的為一跳簇,飛機依簇的簇成員,又叫網(wǎng)關節(jié)點,用于簇間通信。簇頭管理冀據(jù)收到鄰居節(jié)點的ADS-B報文記錄自己的度。Distance為節(jié)點與鄰居節(jié)點的平均距離,其越小說明相應的簇和形成(包括接收一個節(jié)點作為成員),并掌握與鄰居節(jié)點傳輸過程中能量消耗越少,且相對穩(wěn)定。從其所有簇內(nèi)成員的信息。孤兒節(jié)點是一個獨立節(jié)點,不ADs-B報文中獲取飛機位置信息,計算鄰居節(jié)點間的屬于任何簇。在初始成簇之前,所有節(jié)點都處于NULL平均距離狀態(tài),需進行成簇過程。當節(jié)點不處于NULL狀態(tài)時,進行簇維護V(x1+x)2+(0y-y)初始成簇階段的目的是選簇頭,并初始化簇的成員Distance=-4=(3歡迎網(wǎng)上投稿www.chinanet.com《電子技術應用》2013年第39卷第7期Communication and Network根據(jù)權值分簇算法的策略需要,移動節(jié)點需維護一2.3簇維護些信息,用來完成鏈路保持、簇頭選擇及簇的更新維護在Ad-Hoc網(wǎng)絡中,節(jié)點移動造成拓撲頻繁改變,簇工作。此算法中,每個節(jié)點需維護兩個表:自身信息表維護的目的是維持拓撲和簇的穩(wěn)定,包括節(jié)點管理和簇(見表1)和鄰居節(jié)點信息表(見表2)管理表1節(jié)點信息表2.3.1節(jié)點管理(1)節(jié)點加入節(jié)點ID標識節(jié)點的唯一性節(jié)點加入存在兩種情況,即孤兒節(jié)點和新節(jié)節(jié)點狀態(tài)NULL、簇頭、簇成員、孤兒節(jié)點節(jié)點所在簇頭簇成員標識自己的簇頭,簇頭即為自己的ID點的產(chǎn)生(如某一節(jié)點剛開機);分簇后,不屬于任記錄節(jié)點收到簇頭或簇頭收到成員節(jié)點的時間一簇的節(jié)點被標識為孤兒節(jié)點。孤兒節(jié)點和新開時間戳簇大小節(jié)點所在簇擁有的成員數(shù)(對網(wǎng)關節(jié)點和簇頭很有用)機節(jié)點均隨ADS-B報文周期性向鄰居廣播加入節(jié)點度與自己相關的節(jié)點度(對于簇頭而言,節(jié)點度即簇大小)信息 Join_request,攜帶自己的ID和狀態(tài)(孤兒或理想節(jié)點度據(jù)網(wǎng)絡中的拓撲進行初始化NUL),鄰居簇頭收到 Join_request和ADS-B信息平均移動性與所有鄰居節(jié)點相對移動性的平均值后,據(jù)ADS-B判斷此節(jié)點是否符合條件(通過移動平均距離與所有鄰居節(jié)點距離的平均值性、位置判斷),若判斷為滿足加入,簇頭需檢查自權值 weightW。= axkxM+b×u×D+ cxrxDS已的度的門限值(與理想度相差不能大于某一值或表2鄰居節(jié)點信息表等于理想節(jié)點度的2倍)判斷是否接受新節(jié)點:如鄰居節(jié)點ID從 HELLO消息或ADS-B消息獲取果能則向請求節(jié)點發(fā)送確認加人信息 Join_response,攜鄰居節(jié)點狀態(tài)從 HELLO消息獲取帶自身基本信息,請求節(jié)點收到 Join_response后修改狀鄰居節(jié)點簇頭ID從HELO消息獲取,若是孤兒節(jié)點態(tài)為簇成員,并向周圍廣播簇成員信息;若不符合條件,則節(jié)點簇頭為0則簇頭不做響應;若節(jié)點發(fā)出 Join_request超出門限時間鄰居節(jié)點權值從 HELLO消息獲取(用于選擇簇頭)后未收到 Join_response,則認為自己不能加入任何簇,更新狀態(tài)為孤兒節(jié)點。2.2成簇算法描述(1)初始化每個節(jié)點的信息表和鄰居節(jié)點信息表。節(jié)(2)節(jié)點移動或消失點開始處于NUIL狀態(tài),通過接收鄰居節(jié)點ADS-B報此處節(jié)點采用分步式自動判斷自身狀態(tài),如果簇成文,與鄰居節(jié)點交互helo消息,對表進行初始化;通過員一段時間內(nèi)不能收到簇頭的ADS-B消息,則判斷自周期性交換ADS-B報文,節(jié)點n記錄自己的度數(shù)d。己已遠離此簇,修改狀態(tài)為孤兒節(jié)點;如果簇頭一段時間不能收到某個成員的ADS-B消息,則判斷此節(jié)點已(2)每個節(jié)點計算其度數(shù)與理想節(jié)點度D。之差,即經(jīng)離開本簇,將節(jié)點信息從簇成員表中刪除;如果簇頭Dn=dl-Dl。(3每個節(jié)點通過收到的ADS-B報文計算LE,計算到的新節(jié)點的信息數(shù)目,則判斷已脫離原來簇成為普通自己與鄰居節(jié)點的相對移動性M。(4)每個節(jié)點通過收到的ADS-B報文計算自己與郭節(jié)點,設置其狀態(tài)為孤兒狀態(tài),向周圍廣播 join__request居節(jié)點的平均距離DSn。舊成員節(jié)點收到簇頭 Join_request后,修改自身狀態(tài)為孤兒節(jié)點,向周圍廣播 Join_request(5)每個節(jié)點計算權值W。=a×kxM2+b×xDn+cxr×DS;之后將自身信息組成hell消息隨ADS-B報文周期性2.3.2簇管理(1)簇消失:簇頭消失或移動為簇消失,解決方法與向鄰居節(jié)點廣播。節(jié)點移動的處理方法相同。(6)相鄰節(jié)點收到helo消息攜帶的W,后依次進行比較,選其中W。最小的節(jié)點為簇頭,若W。相同,則選(2)簇合并:每個簇有一個最高節(jié)點度(設為理想度ID最小的節(jié)點為簇頭,成為簇頭的節(jié)點向周圍廣播簇的2倍),由于簇頭在廣播自身信息時攜帶了自身簇成頭消息,攜帶自身ID、Wn、節(jié)點度、簇頭狀態(tài),宣布自己己員數(shù),處于兩簇間的網(wǎng)關節(jié)點,根據(jù)收到的多個簇的簇成員數(shù)進行計算,若合并后簇的成員總數(shù)不超過門限成為簇頭。(7)鄰居節(jié)點第一次收到簇頭廣播的簇消息時,將自值,則通過兩個簇頭的W選擇出新的簇頭,向兩簇頭發(fā)身狀態(tài)由NUL設為簇成員,并廣播自身狀態(tài),攜帶自送合并信息,包含自身1,兩端簇頭D簇頭的W、每己和簇頭的1D,聲明已成為某一簇的成員(一個簇成員個簇的成員數(shù)量,簇頭收到信息后,向自己的簇成員發(fā)送合并信息,其中攜帶新簇頭ID,完成兩簇的合并。可同時處于多個簇中,這種成員被標識為網(wǎng)關節(jié)點)3性能評估(8)與所有鄰居節(jié)點不連通,或不能成功加入任一簇為準確刻畫算法性能,需用仿真對4種算法進行比的節(jié)點被標識為孤兒節(jié)點。較。借助NS-2仿真以上算法。在150×150海里的區(qū)域(9)重復步驟(2)-(8),直到所有節(jié)點狀態(tài)標識完。內(nèi)隨機放置200架飛機,飛機移動方向在(0,27)內(nèi)隨機《電子技術應用》2013年第39卷第7期91通信與網(wǎng)絡 Communication and Netw水k分布,由于救災場景下低空飛機速度為400km/h-500km/h因此移動速度在400km/h~500km/h間隨機選擇,飛機間1采用UAT數(shù)據(jù)鏈D,仿真時間為5mm主要采用以下衡as- ADSW1HIGHT量指標:簇頭數(shù)C、單位時間內(nèi)節(jié)點重新加入簇的次數(shù)J04(節(jié)點移動)。4種算法都采用按需更新策略。--LOWMOBILE通過調(diào)整UAT數(shù)據(jù)鏈的覆蓋范圍,查看飛機傳輸范21B0n4即101圍對簇頭數(shù)的影響,覆蓋范圍從20~120海里以10遞增變化;通過修改權重因子,査看其對算法的影響。仿真結圖3節(jié)點重新加入簇的次數(shù)隨數(shù)據(jù)鏈傳輸范圍的變化果如圖2所示, LOWMOBILE為最低移動性算法,HGHr空網(wǎng)絡特性提出了基于權值的成簇算法。該算法利用航為最高節(jié)點度算法,GP為基于位置算法,ADSW和至網(wǎng)絡中的ADS-B應用,綜合考慮移動節(jié)點的三個因ADSW為基于ADS-B報文的權值分簇算法。前者,素,適合新航行系統(tǒng)中作戰(zhàn)或救災場景下飛機共同完成deal=10,a=0.7,b=c=0.2;后者, ideal-=7,a=0.4,b=c任務需組建的Ad-Hoc網(wǎng)絡。通過仿真結果可見,綜合0.3,可比較不同權重因子的ADSW性能。從圖2可知考慮各種因素考慮,提高了成簇速度,減少了簇數(shù)目,節(jié)所有算法中簇頭數(shù)隨數(shù)據(jù)鏈覆蓋范圍的增加而減少,逐點加人新簇的次數(shù)趨于平緩,增強了簇的穩(wěn)定性。適用漸趨于1,當傳輸范圍大于60后,變化速率逐漸降低,于新航行系統(tǒng)中承載ADS-B應用和飛行速度、方向不此結果符合預期,LUAT覆蓋范圍越大,節(jié)點傳輸范圍越定的航空場景大,簇的覆蓋越大。此外,還可看出ADSW的簇頭數(shù)小于參考文蔚其他幾種算法,因為ADSW對簇頭節(jié)點有限制,每個簇1張軍.現(xiàn)代空中交通管理M]北京:北京航空航天大學內(nèi)成員分布較均衡,且ADSW1稍高于ADSW,因為其權出版社,2005重因子b更大。2]鄭少仁,王海濤,趙志峰,等,Ad-Hoc網(wǎng)絡技術[M]北京:人民郵電出版社,20051003]何獻武,基于節(jié)點位置和移動性的分群算法[J].四川兵工學報,2011,32(4):60-64.4]雒寶宏,楊瑞娟,馬曉巖,等.基于群限制的AdHo網(wǎng)絡多跳分群算法!J計算機工程,2008,34(17):120-122數(shù)據(jù)鏈傳輸范圍[5]袁曉晶,張軍,黃智剛.空基與星基組合監(jiān)視系統(tǒng)中的圖2簇頭數(shù)隨數(shù)據(jù)鏈傳輸范圍變化的曲線ADS-B分群算法[J電訊技術,2007,47(1):82-85觀察UAT傳輸范圍對節(jié)點重新加入簇的次數(shù)影響,[6 Su William, LEE S J, GERLA M. Mobility prediction inwireless networks. 0-7803-6521-6/$10.00(C)2000 IEEE.即簇的穩(wěn)定性,場景配置與以上相同,仿真結果見圖3。[71 Fei Huang, Zhang Jun, Zhu Yanbo, Liu wei. Modeling由圖3可知,所有算法中節(jié)點重新加入簇的次數(shù)J隨傳and simulation of an aeronautical sub network based on輸范圍的增長而逐漸減小。UAT傳輸范圍較低時,簇數(shù)universal access transceiver[C]. 2008 Asia Simulation Con目較多,簇內(nèi)節(jié)點數(shù)目少,甚至只有一個簇頭,此時節(jié)點ference-7 Intl. Conf. on Sys. Simulation and Scientific離開原簇概率很小。當傳輸范圍逐漸增大后,J逐漸增(收稿日期:2012-12-25)加并在傳輸范圍為70海里左右達到最大,隨后又開始下降,因為簇覆蓋范圍增大時,節(jié)點移出原簇的概率隨作者簡介之下降;此外,還可看出,ADSW穩(wěn)定性高于 ADSWI,因張海,男,1979年生,碩士,工程師,主要研究方向:新為ADSW的權重a更大,飛機的移動速度對于簇的穩(wěn)定性航行系統(tǒng),數(shù)據(jù)鏈系統(tǒng)。影響較大李綱,男,1974年生,碩士,工程師,主要研究方向:空本文在對已有分簇算法進行分析的基礎上,結合航間目標監(jiān)視技術(上接第88頁)with delay-line and non-linear circuit(for ToT)[JI成都:成都理工大學,2008Nuclear Instruments and Methods in Physics Research A[2]王敏數(shù)字核能譜測量系統(tǒng)中濾波與成形技術研究[D](2011)S24-S27(收稿日期:2013-03-03)成都:成都理工大學,2012[3]肖無云,魏義祥,艾憲蕓.數(shù)字化多道脈沖幅度分析中的作者簡介梯形成形算法[J清華大學學報(自然科學版),2005,45王敏,女,1975年生,講師,博士,主要研究方向:核輻(6):810-812射測量技術及核測量儀器研究[4] ORITA T, TAKAHASHI H. A new pulse width signal pro歡迎網(wǎng)上投稿www.chinaaet.com《電子技術應用》2013年第39卷第7期