ADS-B技術[1]是未來航空監(jiān)視的主要手段之一，它以地空/空空數(shù)據(jù)鏈為通信手段，以導航系統(tǒng)及其他機載設備產(chǎn)生的信息為數(shù)據(jù)源，由具有 ADS-B功能的飛機將自身的位置、速度等SV(State Vector)信息周期性對外廣播，地面站和其他飛機接收這些報文，進行飛機間的通信和監(jiān)控。

    隨著飛機性能和數(shù)量的提高，ADS-B應用不斷升級[1]，對其覆蓋范圍有了更高要求。移動自組網(wǎng)(Ad-Hoc)技術能有效解決這一問題。Ad-Hoc是一種自組織的無線多跳網(wǎng)，組網(wǎng)無需固定路由器，所有節(jié)點均移動，并能以任意方式動態(tài)地與其他節(jié)點保持聯(lián)系。在航空Ad-Hoc網(wǎng)絡中，由于數(shù)據(jù)鏈覆蓋范圍有限導致兩個無法通信的飛機可借助其他節(jié)點轉發(fā)進行通信,擴大了ADS-B的覆蓋范圍。
    由于Ad-Hoc采用共享無線信道方式工作,過多節(jié)點競爭有限的無線信道,增加了發(fā)生碰撞的概率。為減少共享相同信道的節(jié)點數(shù)目、降低碰撞概率、提高信道利用率,須對移動節(jié)點進行分簇[2-4]，以提高通信質(zhì)量。
    本文提出了一種基于ADS-B 報文，綜合移動性、位置、節(jié)點度特點，采用權值進行評估的分簇算法。
    圖1為航空Ad-Hoc網(wǎng)，簇內(nèi)飛機可直接通信，簇間飛機通過網(wǎng)關通信，相隔太遠的簇借助基站中繼轉發(fā)進行通信，為增強信道利用率，通過簇頭將信息轉發(fā)給基站。

1 傳統(tǒng)分簇算法
    目前存在很多分簇算法，算法直接影響簇的穩(wěn)定性、大小以及節(jié)點擔任簇頭的時間，從而影響生成簇和維護簇所需開銷[2-3,5]。
    最大連接度算法[2]盡可能減少了路由器的數(shù)目。其思想是,節(jié)點間通過交換控制信息得到鄰居節(jié)點的數(shù)目，該節(jié)點和其鄰居節(jié)點中具有最大度的被選為簇頭，度數(shù)相同時，選ID最小的作為簇頭，簇頭的一跳鄰居節(jié)點為該簇普通成員。其優(yōu)點是簇數(shù)目較少，減少分組投遞時延，但信道空間重用率較低。
    最低移動性算法[2-3]盡量保持了簇結構的穩(wěn)定性,其思想是節(jié)點的移動性越高，其權重越低，選最高權重的節(jié)點作為簇頭。該算法需要一種機制來量化節(jié)點的移動性，簡單的方法是通過節(jié)點間相對速度絕對值的時間平均來衡量節(jié)點的相對移動性。
    基于地理位置的算法[2-3]是按地理區(qū)域劃分簇結構，使地理位置上較靠近的節(jié)點組成簇。其思想是節(jié)點通過交互位置信息確定本地的網(wǎng)絡拓撲，然后依據(jù)鄰居節(jié)點的分布來選擇簇頭并形成簇。此方法可減少簇頭和簇內(nèi)節(jié)點間通信的總功率和平均傳輸時延，但并非所有節(jié)點都可獲得節(jié)點位置信息。
    以上算法往往只考慮系統(tǒng)中節(jié)點的某一特性，應用場合受限，簇的性能較差。由于飛機高速移動和方向不定,不能只考慮某一因素。飛機周期性發(fā)送ADS-B報文，其攜帶飛機SV[1]信息，因此，本文提出一種基于ADS-B報文的分簇算法，將以上幾種傳統(tǒng)算法進行加權來進行成簇和簇維護。
2 基于ADS-B報文的分簇算法
    在成簇算法中，由于網(wǎng)絡拓撲動態(tài)變化[2]，需維護節(jié)點的角色信息，如：簇頭、簇成員、孤兒和NULL。簇成員是簇的基本節(jié)點，實現(xiàn)簇內(nèi)節(jié)點的基本通信，屬于不同簇的簇成員，又叫網(wǎng)關節(jié)點，用于簇間通信。簇頭管理其相應的簇和形成(包括接收一個節(jié)點作為成員)，并掌握其所有簇內(nèi)成員的信息。孤兒節(jié)點是一個獨立節(jié)點，不屬于任何簇。在初始成簇之前，所有節(jié)點都處于NULL狀態(tài)，需進行成簇過程。當節(jié)點不處于NULL狀態(tài)時，進行簇維護。
    初始成簇階段的目的是選簇頭，并初始化簇的成員關系。此時，已在一個簇中的節(jié)點可能離開所在的簇加入別的簇，而簇頭可能進入別的簇頭的范圍或被毀，簇維護是對初始簇形成后上述事件的補救。
    下面將描述所提出的成簇算法，包括成簇采用的度量、成簇算法和簇維護。
2.1 簇的度量權值weight的定義
    分簇算法要求簇能很好地適應網(wǎng)絡拓撲的動態(tài)變化，在航空網(wǎng)絡中，由于飛機高速移動，移動方向不定，飛機的移動性對簇的穩(wěn)定性有很大影響。同時位置信息反映鄰居節(jié)點間的距離，通過位置信息和節(jié)點度能很好地選擇簇頭，防止選擇邊緣節(jié)點作為簇頭造成簇的不穩(wěn)定。因此，本文提出一種基于多種因素的權值計算方法，權值為：

    根據(jù)權值分簇算法的策略需要, 移動節(jié)點需維護一些信息, 用來完成鏈路保持、 簇頭選擇及簇的更新維護工作。此算法中，每個節(jié)點需維護兩個表：自身信息表(見表1)和鄰居節(jié)點信息表(見表2)。

2.2 成簇算法描述
    (1)初始化每個節(jié)點的信息表和鄰居節(jié)點信息表。節(jié)點開始處于NULL狀態(tài)，通過接收鄰居節(jié)點ADS-B報文，與鄰居節(jié)點交互hello消息，對表進行初始化；通過周期性交換ADS-B報文，節(jié)點n記錄自己的度數(shù)dn。
   (2)每個節(jié)點計算其度數(shù)與理想節(jié)點度Dideal之差，即Dn=|dn-Dideal|。
   (3)每個節(jié)點通過收到的ADS-B報文計算LET，計算自己與鄰居節(jié)點的相對移動性Mn。
   (4)每個節(jié)點通過收到的ADS-B報文計算自己與鄰居節(jié)點的平均距離DSn。
   (5)每個節(jié)點計算權值Wn=a×k×Mn+b×w×Dn+c×r×DSn；之后將自身信息組成hello消息隨ADS-B報文周期性向鄰居節(jié)點廣播。
　(6)相鄰節(jié)點收到hello消息攜帶的Wn后依次進行
比較，選其中Wn最小的節(jié)點為簇頭，若Wn相同，則選ID最小的節(jié)點為簇頭，成為簇頭的節(jié)點向周圍廣播簇頭消息，攜帶自身ID、Wn、節(jié)點度、簇頭狀態(tài)，宣布自己成為簇頭。
    (7)鄰居節(jié)點第一次收到簇頭廣播的簇消息時，將自身狀態(tài)由NULL設為簇成員，并廣播自身狀態(tài)，攜帶自己和簇頭的ID，聲明已成為某一簇的成員(一個簇成員可同時處于多個簇中，這種成員被標識為網(wǎng)關節(jié)點)。
　(8)與所有鄰居節(jié)點不連通，或不能成功加入任一簇的節(jié)點被標識為孤兒節(jié)點。
　(9)重復步驟(2)~(8)，直到所有節(jié)點狀態(tài)標識完。
2.3 簇維護
　 在Ad-Hoc網(wǎng)絡中，節(jié)點移動造成拓撲頻繁改變，簇維護的目的是維持拓撲和簇的穩(wěn)定，包括節(jié)點管理和簇管理。
2.3.1 節(jié)點管理
    (1) 節(jié)點加入
    節(jié)點加入存在兩種情況，即孤兒節(jié)點和新節(jié)點的產(chǎn)生(如某一節(jié)點剛開機)；分簇后，不屬于任一簇的節(jié)點被標識為孤兒節(jié)點。孤兒節(jié)點和新開機節(jié)點均隨ADS-B報文周期性向鄰居廣播加入信息join_request，攜帶自己的ID和狀態(tài)(孤兒或NULL)，鄰居簇頭收到join_request和ADS-B信息后，據(jù)ADS-B判斷此節(jié)點是否符合條件(通過移動性、位置判斷)，若判斷為滿足加入，簇頭需檢查自己的度的門限值(與理想度相差不能大于某一值或等于理想節(jié)點度的2倍)判斷是否接受新節(jié)點：如果能則向請求節(jié)點發(fā)送確認加入信息Join_response，攜帶自身基本信息，請求節(jié)點收到Join_response后修改狀態(tài)為簇成員，并向周圍廣播簇成員信息；若不符合條件，則簇頭不做響應；若節(jié)點發(fā)出join_request超出門限時間后未收到Join_response，則認為自己不能加入任何簇，更新狀態(tài)為孤兒節(jié)點。
    (2)節(jié)點移動或消失
    此處節(jié)點采用分步式自動判斷自身狀態(tài)，如果簇成員一段時間內(nèi)不能收到簇頭的ADS-B消息，則判斷自己已遠離此簇，修改狀態(tài)為孤兒節(jié)點；如果簇頭一段時間不能收到某個成員的ADS-B消息，則判斷此節(jié)點已經(jīng)離開本簇，將節(jié)點信息從簇成員表中刪除；如果簇頭節(jié)點一段時間內(nèi)收到簇成員的ADS-B報文數(shù)目小于收到的新節(jié)點的信息數(shù)目，則判斷已脫離原來簇成為普通節(jié)點，設置其狀態(tài)為孤兒狀態(tài)，向周圍廣播join_request，舊成員節(jié)點收到簇頭join_request后，修改自身狀態(tài)為孤兒節(jié)點，向周圍廣播join_request。
2.3.2 簇管理
    (1)簇消失:簇頭消失或移動為簇消失，解決方法與節(jié)點移動的處理方法相同。
    (2)簇合并:每個簇有一個最高節(jié)點度（設為理想度的2倍），由于簇頭在廣播自身信息時攜帶了自身簇成員數(shù),處于兩簇間的網(wǎng)關節(jié)點，根據(jù)收到的多個簇的簇成員數(shù)進行計算，若合并后簇的成員總數(shù)不超過門限值，則通過兩個簇頭的Wn選擇出新的簇頭，向兩簇頭發(fā)送合并信息，包含自身ID、兩端簇頭ID、簇頭的Wn、每個簇的成員數(shù)量，簇頭收到信息后，向自己的簇成員發(fā)送合并信息，其中攜帶新簇頭ID，完成兩簇的合并。
3 性能評估
    為準確刻畫算法性能，需用仿真對4種算法進行比較。借助NS-2仿真以上算法。在150×150海里的區(qū)域內(nèi)隨機放置200架飛機,飛機移動方向在(0,2?仔)內(nèi)隨機分布,由于救災場景下低空飛機速度為400 km/h-500 km/h，因此移動速度在400 km/h~500 km/h間隨機選擇,飛機間采用UAT數(shù)據(jù)鏈[7]，仿真時間為5 min。主要采用以下衡量指標：簇頭數(shù)C、單位時間內(nèi)節(jié)點重新加入簇的次數(shù)J(節(jié)點移動)。4種算法都采用按需更新策略。
    通過調(diào)整UAT數(shù)據(jù)鏈的覆蓋范圍，查看飛機傳輸范圍對簇頭數(shù)的影響，覆蓋范圍從20~120海里以10遞增變化；通過修改權重因子，查看其對算法的影響。仿真結果如圖2所示,LOWMOBILE為最低移動性算法，HIGHT為最高節(jié)點度算法，GP為基于位置算法，ADSW和ADSW1為基于ADS-B報文的權值分簇算法。前者，ideal=10，a=0.7，b=c=0.2；后者，ideal=7，a=0.4，b=c=0.3，可比較不同權重因子的ADSW性能。從圖2可知，所有算法中簇頭數(shù)隨數(shù)據(jù)鏈覆蓋范圍的增加而減少，逐漸趨于1，當傳輸范圍大于60后，變化速率逐漸降低，此結果符合預期，UAT覆蓋范圍越大，節(jié)點傳輸范圍越大，簇的覆蓋越大。此外，還可看出ADSW的簇頭數(shù)小于其他幾種算法，因為ADSW對簇頭節(jié)點有限制，每個簇內(nèi)成員分布較均衡，且ADSW1稍高于ADSW，因為其權重因子b更大。

    觀察UAT傳輸范圍對節(jié)點重新加入簇的次數(shù)影響，即簇的穩(wěn)定性，場景配置與以上相同，仿真結果見圖3。由圖3可知，所有算法中節(jié)點重新加入簇的次數(shù)J隨傳輸范圍的增長而逐漸減小。UAT傳輸范圍較低時，簇數(shù)目較多，簇內(nèi)節(jié)點數(shù)目少，甚至只有一個簇頭，此時節(jié)點離開原簇概率很小。當傳輸范圍逐漸增大后，J逐漸增加并在傳輸范圍為70海里左右達到最大，隨后又開始下降，因為簇覆蓋范圍增大時，節(jié)點移出原簇的概率隨之下降；此外，還可看出，ADSW穩(wěn)定性高于ADSW1，因為ADSW的權重a更大,飛機的移動速度對于簇的穩(wěn)定性影響較大。

    本文在對已有分簇算法進行分析的基礎上，結合航空網(wǎng)絡特性提出了基于權值的成簇算法。該算法利用航空網(wǎng)絡中的ADS-B應用，綜合考慮移動節(jié)點的三個因素，適合新航行系統(tǒng)中作戰(zhàn)或救災場景下飛機共同完成任務需組建的Ad-Hoc網(wǎng)絡。通過仿真結果可見，綜合考慮各種因素考慮，提高了成簇速度，減少了簇數(shù)目，節(jié)點加入新簇的次數(shù)趨于平緩，增強了簇的穩(wěn)定性。適用于新航行系統(tǒng)中承載ADS-B應用和飛行速度、方向不定的航空場景。
參考文獻
[1] 張軍. 現(xiàn)代空中交通管理[M].北京：北京航空航天大學出版社，2005.
[2] 鄭少仁,王海濤,趙志峰,等.Ad-Hoc網(wǎng)絡技術[M].北京:人民郵電出版社，2005.
[3] 何獻武.基于節(jié)點位置和移動性的分群算法[J].四川兵工學報，2011，32(4):60-64.
[4] 雒寶宏，楊瑞娟，馬曉巖，等.基于群限制的 Ad Hoc 網(wǎng)絡多跳分群算法[J].計算機工程，2008,34(17):120-122.
[5] 袁曉晶,張軍,黃智剛.空基與星基組合監(jiān)視系統(tǒng)中的ADS-B分群算法[J].電訊技術，2007,47(1):82-85.
[6] Su William, LEE S J, GERLA M. Mobility prediction in  wireless networks.0-7803-6521-6/$10.00(C) 2000 IEEE.
[7] Fei Huang, Zhang Jun, Zhu Yanbo, Liu Wei. Modeling  and simulation of an aeronautical sub network based on universal access transceiver[C]. 2008 Asia Simulation Conference-7 Intl. Conf. on Sys. Simulation and Scientific  Computing.