第32卷第4期計算機應(yīng)用研究Vol 32 No 42015年4月Application Research of ComputersApr.2015高動態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計代家銘!,宋玉龍2,尚亞黎,李冬濤,羅長遠2(1.解放軍65012部隊,沈陽1100002.信息工程大學(xué),鄭州45000摘要:分簇是解決航空自組網(wǎng)擴展性差的重要手段,針對軍用飛機高動態(tài)造成簇結(jié)構(gòu)不穩(wěn)定的情況,設(shè)計一種基于地理位置的分簇算法。該算法從位置和運動的角度構(gòu)造了備份簇首選擇因子,采用備份簇首的方法保證簇結(jié)構(gòu)的穩(wěn)定性;設(shè)立簇容量和簇員篩選因子控制簇規(guī)模,通過附屬簇員避免孤立通信節(jié)點產(chǎn)生,利用網(wǎng)關(guān)使簇形戍網(wǎng)狀結(jié)構(gòu),并理論分析了算法的有效性。最后,仿真驗證其性能,結(jié)果表明,與其他算法相比,該算法可以減少高動態(tài)下簇首更換頻率控制成簇數(shù)量,增強簇抗毀性,有效地提高了簇的整體穩(wěn)定性,更適合應(yīng)用在軍事航空領(lǐng)域。關(guān)鍵詞:航空自組網(wǎng);軍事航空;分簇算法;備份簇首;附屬簇員中圖分類號:TP93文獻標志碼:A文章編號:1001-3695(2015)04-1193-06doi:10.3969/jiss.10013695.2015.04.055Cluster algorithm for aeronautical Ad hoc network in highly dynamic environmentDAI Jia-ming, SONG Yu-long, SHANG Ya-li,LI(1. 65012 Troop of PLA, Shenyang 110000, China; 2. Information Engineering University, Zhengzhou 450001, China)Abstract: Clustering is an important way to solve the scalability of aeronautical Ad hoc network( AANET). For instability ofcluster structure caused by high dynamic, this paper designed a clustering algorithm which was based on location information formilitary aircraft. The algorithm combined the actual situation to establish a military aircraft flight models, from the perspectiveof location and movement of tectonic backup cluster head selection factor, which used a backup method of cluster heads to en-sure the stability of cluster structure. It established capacity of cluster and cluster member filter factor to control its size, usedgateway and ancillary cluster members to establish the mesh structure of network and avoid isolating communication node, thenanalyzed the algorithm theoretically. Finally, the simulation results show that the algorithm can reduce the frequency of clusterhead replacement, control the number of clusters and enhance its survivability, effectively improving the overall stability of thecluster. It is more suitable for applications in the field of military aviationKey words: AANET; military aviation; clustering algorithm; backup cluster head; ancillary cluster member種具有時延感知的分簇算法但沒有注意延長網(wǎng)絡(luò)壽命,而0引言且設(shè)定所有節(jié)點數(shù)據(jù)的時隙寬度相等的條件過于理想;文獻航空自組網(wǎng)(ANET)是移動自組網(wǎng)在航空領(lǐng)域的拓展與[10]在蜂窩結(jié)構(gòu)的基礎(chǔ)上,利用感知位置信息的方法進行分應(yīng)用,由于具備自組織自修復(fù)的能力和快速高效組網(wǎng)的優(yōu)簇,但其只適合靜態(tài)網(wǎng)絡(luò);文獻[11)從節(jié)點編號、節(jié)點度及勢而特別適合解決軍事航空中飛行環(huán)境惡劣高動態(tài)拓撲、公平度等角度選擇簇首,算法較為簡單且便于維護但當(dāng)節(jié)點節(jié)點不穩(wěn)定地面設(shè)施保障困難等問題,可為軍航通信發(fā)揮抗移動性增強時,節(jié)點簇內(nèi)生存時間急劇下降僅適用于低速移動環(huán)境;文獻[13]通過估計節(jié)點速度、引入虛擬中心、預(yù)警簇毀、補盲支持編隊戰(zhàn)術(shù)協(xié)同等作用,從而大幅提升作戰(zhàn)平臺的頭失效分頻通信等方法設(shè)計了適合中高速環(huán)境下的分簇算戰(zhàn)術(shù)效能2,因此國內(nèi)外許多項目及單位對其進行研究如法,但如果節(jié)點數(shù)量較大或不穩(wěn)定時,容易造成頻段空白頻譜美國的TN歐盟的 NEWSKY項目,以及國內(nèi)的空軍工程、北資源枯竭的情況;文獻[14]運用層次分析法對篪首進行選擇京航空航天大學(xué)等單位形成一種空間信息網(wǎng)成簇方法,不過其剩余能量、功率水平等不過ANET使路由協(xié)議、Q0s保障“及可擴展性等面參數(shù)不適合軍機:文獻[5].用設(shè)立意愿因子方法選舉簇首臨新的困難。為解決這些問題研究人員提出將網(wǎng)絡(luò)劃分提出了適合高動態(tài)移動網(wǎng)絡(luò)的自適應(yīng)穩(wěn)定分簇算法但該方法成組的方法即分簇算法采用分簇的結(jié)構(gòu)可以很大程度地解沒有考慮軍用飛機被擊落等突發(fā)情況對簇結(jié)構(gòu)穩(wěn)定性的影響決擴展性差等問題,從而提高網(wǎng)絡(luò)的性能和效率雖然目前對分簇算法的研究較深入,但其設(shè)計目標需滿足現(xiàn)已有最小、最大連通度等多種較為成熟的分簇算特定的要求并適用于相應(yīng)的環(huán)境而軍事航空自組網(wǎng)具有以下法,它們從權(quán)值設(shè)定地理位置能量大小等多個角度對簇的建不同于一般自組網(wǎng)的特點:立進行研究。文獻[8]為增加網(wǎng)絡(luò)生存時間基于節(jié)點連接度a)分布場景大尺度和不確定性。飛機廣泛分布在大洋、采用自適應(yīng)調(diào)節(jié)通信范圍等方法減少能量損耗;文獻[9]提出沙漠等無地面中轉(zhuǎn)站的區(qū)域。收稿日期:2014-03-02;修回日期:201404-28基金項目:全軍軍事學(xué)研究生課題作者簡介:代家銘(1989-),男,黑龍江佳木斯人,助理工程師,主要研究方向為信息安全(djm198805@163.com);宋玉龍(1988-),男,黑龍江大慶人,碩士研究生,主要研究方向為無線通信;尚亞黎(1974-),女,高級工程師,碩士,主要研究方向為信息安金;李冬濤(1978-),男,工程師,碩士主要研究方向為信息安全;羅長遠(1973-),男,副教授,博士,主要研究方向為無線通信1194·計算機應(yīng)用研究第32卷b)運動階段性。飛機在巡航作戰(zhàn)等不同階段的運動方首直接通信的未入簇節(jié)點。式、飛機相對位置等均存在很大的差異。附屬簇員具有一定的靈活性,其可通過簇員與別的節(jié)點進c)拓撲的高動態(tài)性。飛機的速度可達3.5Mach,節(jié)點高行通信,從而避免了孤立通信節(jié)點的產(chǎn)生。如圖1中,單跳簇速移動會造成網(wǎng)絡(luò)拓撲快速變化,直接影響到MAC協(xié)議、路由的附屬節(jié)點9可通過簇員8與其他節(jié)點通信。另外,由于其只協(xié)議等方面性能。與簇員通信而不參與簇內(nèi)的信息交互所以不會增加簇的額外d)節(jié)點分布不規(guī)則。由于作戰(zhàn)任務(wù)的差異,導(dǎo)致不同空開銷減少了簇首的負載同時,可以使簇首與簇員達到負載域飛機數(shù)量、密度等相差較大均衡。e)不可預(yù)測性。在空戰(zhàn)中飛機存在時刻被擊落的可能,定義3備份簇首。通過一定規(guī)則篩選得到且有潛力成地面中轉(zhuǎn)站等同樣面臨被銷毀的危險另外,在作戰(zhàn)區(qū)域內(nèi)飛為簇首的節(jié)點行軌跡等也存在不可預(yù)測性。備份簇首在簇首未失效前充當(dāng)簇員的角色,一旦簇首由于f)節(jié)點能量不受限?？諔?zhàn)持續(xù)時間通常為幾個小時,軍機被擊落等原因不能維護簇的正常通信時,為避免因簇首失效產(chǎn)會提供足夠的用于通信的能量,因此,不需要考慮節(jié)點通信能生的簇動蕩,此時備份簇首自動成為初始簇首并具有簇首的功量耗竭的情況能,從而保障了簇的穩(wěn)定性。通過以上分析如果不結(jié)合軍事航空自組網(wǎng)的特性而建立定義4簇容量N。簇保持最佳狀態(tài)時簇員的數(shù)量。的分簇算法,可能會造成不必要的開銷和資源的浪費,甚至使當(dāng)網(wǎng)絡(luò)中具有一定數(shù)量的節(jié)點時如果簇的簇員數(shù)量過通信中斷。本文以軍機為研究對象通過收集節(jié)點地理位置信小,則簇首的簇間開銷會因簇數(shù)量過多而很大;反之,則會造成息,計算理想簇首節(jié)點據(jù)此選取穩(wěn)定性優(yōu)先的備份簇首以避簇內(nèi)簇首負載很大免簇的振蕩,在單跳簇的基礎(chǔ)上,運用簇容量控制簇的規(guī)模,利定義5簇首閾值6。判斷節(jié)點成為簇首的最低標準。用附屬簇員減少孤立通信節(jié)點產(chǎn)生,建立一種適合軍事航空自組網(wǎng)的分簇算法。最后,對各種指標進行仿真驗證。簇首閾值可增加簇的穩(wěn)定性及減少簇首的更換次數(shù),其設(shè)定須考慮簇的規(guī)模、相對運動等因素。基本定義2初始簇的建立相關(guān)假設(shè)定義6初始簇。節(jié)點在簇更新前形成的簇。為方便研究提出以下合理假設(shè):由于軍機在執(zhí)行巡航等任務(wù)時,通常以一定的編制為單a)所有飛機均為同質(zhì)飛機(性能相同)且均有唯一的I位,如飛機中隊等同一編制內(nèi)飛機數(shù)量往往在10架以內(nèi)并且標志記為ID1,ID2,…,ID。根據(jù)定位系統(tǒng)或者其他手段可以它們的任務(wù)相同或相似。因此,飛機間的相對速度、相對位置獲得自身的地理位置信息M1,M2,…,M,其中,M由位置坐較為穩(wěn)定故可將其默認為同一個簇。另外同一編制內(nèi)的飛標和速度矢量組成機之間(如長機和僚機)存在著指揮關(guān)系,并且長機的飛行位b)飛機間通過公共信道進行分簇而分簇后則使用不同置常位于機群的中心且與僚機的通信量相對較多所以可令長信道通信機為最開始的初始簇首,僚機成為簇員,簇首建立簇的成員列c)由于飛機飛行高度的變化通常為幾千米而飛行通信表從而完成簇的初始化工作。由于此過程飛機間相對位置較半徑為幾百千米故忽略飛機飛行的高度變化。為穩(wěn)定只需要交換成簇信息便可進行分簇因此,不作為本文1.2相關(guān)定義研究重點。定義1單跳簇。簇首到所有簇員的距離為一跳的簇。3算法描述單跳簇的任意兩簇員之間的最大距離為兩跳。同理如果簇首到所有簇員的距離為多跳時,則該簇為多跳簇。在圖13.1備份簇首的選舉中,實線內(nèi)的簇為單跳簇,虛線為兩跳簇。當(dāng)簇跳數(shù)較多時,其初始簇中的初始簇首s向其鄰節(jié)點發(fā)送廣播信息,并通過內(nèi)的簇員數(shù)量也會增大。例如,當(dāng)軍機的通信半徑為300km,收集應(yīng)答信息建立鄰居表;隨后,根據(jù)鄰居表里的位速信息計若形成3跳簇,其簇的半徑便可達到900km,此時,簇會覆蓋算理想節(jié)點及包括s在內(nèi)的所有節(jié)點的備份簇首選擇因子據(jù)作戰(zhàn)區(qū)域內(nèi)的絕大部分飛機簇內(nèi)開銷急劇增大進而便失去分此尋找備份簇首。簇的意義。令5的初始位速信息為M,=[(x,y,),(,,)],當(dāng)s收到n個鄰節(jié)點的位速信息M1=[(x1,y1),("x),"tu,)],,M,=[(x,,),(v,,)]后可以計算出理想節(jié)點o的位速信息M。=[(x,y,),(vm,),o,)],具體計算為①首M,=rx+、"一,”)](1)由式(1)可知,理想節(jié)點o的地理位置為所有鄰節(jié)點的中心,其速度反映了所有鄰節(jié)點的整體運動趨勢圖1單雙跳簇示意圖為保證簇的穩(wěn)定,所選取的備份簇首應(yīng)與簇的整體運動趨勢相吻合且最好位于簇的中心。由于各節(jié)點為同質(zhì)節(jié)點,那么定義2附屬簇員?？膳c簇員直接通信但不可與該簇簇備份簇首的選擇便取決于節(jié)點的位置和運動,因此,備份簇首第4期代家銘,等:高動態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計1195·選擇指標,需要結(jié)合節(jié)點的位置和運動兩方面因素。均運動因子,結(jié)合式(8)所得的值即為簇首閾值,即1)位置因子定義7若兩節(jié)點間的距離在一跳范圍內(nèi),則兩者互為鄰(9)節(jié)點3.2簇員的篩選定義8符號 degreel(i)表示節(jié)點i的度,其數(shù)值等于i跳距離內(nèi)鄰節(jié)點的數(shù)量。當(dāng)某節(jié)點成為簇首后,若其簇員超過簇容量時,則需要通節(jié)點的度可以衡量其在簇中的位置及與其他節(jié)點的連通過簇員篩選因子對節(jié)點是否可成為簇員進行判斷和篩選。若狀況某節(jié)點的度越大其位置越靠近中心),即更適合成為保持現(xiàn)有速度,節(jié)點間且能通信的保持時間可反映其穩(wěn)定程備份簇首。因此,將位置因子定義為節(jié)點度的大小。度,于是,將鄰節(jié)點通信保持時間作為簇員篩選因子v。若初始簇首的鄰節(jié)點較多,當(dāng)計算每個節(jié)點的度時,其計不妨令a為簇首,任取飛機i,則其簇員篩選因子為y。算量較大,而通過理想節(jié)點的計算公式可知,度較大的節(jié)點距由圖3可知下式成立離理想節(jié)點較近,所以初始簇首s可在距離理想節(jié)點R2的圓(ay+b)2+(cy+d)2=R2形范圍內(nèi)尋找備份簇首。)R2-(ad-b)2設(shè)某節(jié)點i的m個鄰節(jié)點組成的集合為Mi],其可用一其中:0=U(,b=x一x,=,-(m,d=y.-y。個1×的鄰接矩陣A=[a]1來表示,元素a關(guān)系式為10