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

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

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

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

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

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

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