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

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

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

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

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

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

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