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

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

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

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

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

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

    本文在對已有分簇算法進行分析的基礎上，結合航空網絡特性提出了基于權值的成簇算法。該算法利用航空網絡中的ADS-B應用，綜合考慮移動節點的三個因素，適合新航行系統中作戰或救災場景下飛機共同完成任務需組建的Ad-Hoc網絡。通過仿真結果可見，綜合考慮各種因素考慮，提高了成簇速度，減少了簇數目，節點加入新簇的次數趨于平緩，增強了簇的穩定性。適用于新航行系統中承載ADS-B應用和飛行速度、方向不定的航空場景。
參考文獻
[1] 張軍. 現代空中交通管理[M].北京：北京航空航天大學出版社，2005.
[2] 鄭少仁,王海濤,趙志峰,等.Ad-Hoc網絡技術[M].北京:人民郵電出版社，2005.
[3] 何獻武.基于節點位置和移動性的分群算法[J].四川兵工學報，2011，32(4):60-64.
[4] 雒寶宏，楊瑞娟，馬曉巖，等.基于群限制的 Ad Hoc 網絡多跳分群算法[J].計算機工程，2008,34(17):120-122.
[5] 袁曉晶,張軍,黃智剛.空基與星基組合監視系統中的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.