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é)點均移動,，并能以任意方式動態(tài)地與其他節(jié)點保持聯(lián)系。在航空Ad-Hoc網(wǎng)絡(luò)中,，由于數(shù)據(jù)鏈覆蓋范圍有限導(dǎo)致兩個無法通信的飛機(jī)可借助其他節(jié)點轉(zhuǎn)發(fā)進(jìn)行通信,擴(kuò)大了ADS-B的覆蓋范圍,。
    由于Ad-Hoc采用共享無線信道方式工作,過多節(jié)點競爭有限的無線信道,增加了發(fā)生碰撞的概率。為減少共享相同信道的節(jié)點數(shù)目,、降低碰撞概率、提高信道利用率,須對移動節(jié)點進(jìn)行分簇[2-4],，以提高通信質(zhì)量,。
    本文提出了一種基于ADS-B 報文，綜合移動性,、位置,、節(jié)點度特點，采用權(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é)點擔(dān)任簇頭的時間，從而影響生成簇和維護(hù)簇所需開銷[2-3,5],。
    最大連接度算法[2]盡可能減少了路由器的數(shù)目,。其思想是,節(jié)點間通過交換控制信息得到鄰居節(jié)點的數(shù)目，該節(jié)點和其鄰居節(jié)點中具有最大度的被選為簇頭,，度數(shù)相同時,，選ID最小的作為簇頭，簇頭的一跳鄰居節(jié)點為該簇普通成員,。其優(yōu)點是簇數(shù)目較少,，減少分組投遞時延，但信道空間重用率較低,。
    最低移動性算法[2-3]盡量保持了簇結(jié)構(gòu)的穩(wěn)定性,其思想是節(jié)點的移動性越高,，其權(quán)重越低，選最高權(quán)重的節(jié)點作為簇頭,。該算法需要一種機(jī)制來量化節(jié)點的移動性,，簡單的方法是通過節(jié)點間相對速度絕對值的時間平均來衡量節(jié)點的相對移動性。
    基于地理位置的算法[2-3]是按地理區(qū)域劃分簇結(jié)構(gòu),，使地理位置上較靠近的節(jié)點組成簇,。其思想是節(jié)點通過交互位置信息確定本地的網(wǎng)絡(luò)拓?fù)洌缓笠罁?jù)鄰居節(jié)點的分布來選擇簇頭并形成簇,。此方法可減少簇頭和簇內(nèi)節(jié)點間通信的總功率和平均傳輸時延,，但并非所有節(jié)點都可獲得節(jié)點位置信息。
    以上算法往往只考慮系統(tǒng)中節(jié)點的某一特性,，應(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é)點的角色信息，如：簇頭,、簇成員,、孤兒和NULL。簇成員是簇的基本節(jié)點,，實現(xiàn)簇內(nèi)節(jié)點的基本通信,，屬于不同簇的簇成員,，又叫網(wǎng)關(guān)節(jié)點，用于簇間通信,。簇頭管理其相應(yīng)的簇和形成(包括接收一個節(jié)點作為成員),，并掌握其所有簇內(nèi)成員的信息。孤兒節(jié)點是一個獨(dú)立節(jié)點,，不屬于任何簇,。在初始成簇之前，所有節(jié)點都處于NULL狀態(tài),，需進(jìn)行成簇過程,。當(dāng)節(jié)點不處于NULL狀態(tài)時，進(jìn)行簇維護(hù),。
    初始成簇階段的目的是選簇頭,，并初始化簇的成員關(guān)系。此時,，已在一個簇中的節(jié)點可能離開所在的簇加入別的簇,，而簇頭可能進(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é)點間的距離,，通過位置信息和節(jié)點度能很好地選擇簇頭,，防止選擇邊緣節(jié)點作為簇頭造成簇的不穩(wěn)定。因此,，本文提出一種基于多種因素的權(quán)值計算方法，權(quán)值為：

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

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

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

    本文在對已有分簇算法進(jìn)行分析的基礎(chǔ)上,，結(jié)合航空網(wǎng)絡(luò)特性提出了基于權(quán)值的成簇算法,。該算法利用航空網(wǎng)絡(luò)中的ADS-B應(yīng)用，綜合考慮移動節(jié)點的三個因素,，適合新航行系統(tǒng)中作戰(zhàn)或救災(zāi)場景下飛機(jī)共同完成任務(wù)需組建的Ad-Hoc網(wǎng)絡(luò),。通過仿真結(jié)果可見，綜合考慮各種因素考慮,，提高了成簇速度,，減少了簇數(shù)目，節(jié)點加入新簇的次數(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é)點位置和移動性的分群算法[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.