第32卷第4期計(jì)算機(jī)應(yīng)用研究Vol 32 No 42015年4月Application Research of ComputersApr.2015高動(dòng)態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計(jì)代家銘!,宋玉龍2,尚亞黎,李冬濤,羅長(zhǎng)遠(yuǎn)2(1.解放軍65012部隊(duì),沈陽(yáng)1100002.信息工程大學(xué),鄭州45000摘要:分簇是解決航空自組網(wǎng)擴(kuò)展性差的重要手段,針對(duì)軍用飛機(jī)高動(dòng)態(tài)造成簇結(jié)構(gòu)不穩(wěn)定的情況,設(shè)計(jì)一種基于地理位置的分簇算法。該算法從位置和運(yùn)動(dòng)的角度構(gòu)造了備份簇首選擇因子,采用備份簇首的方法保證簇結(jié)構(gòu)的穩(wěn)定性;設(shè)立簇容量和簇員篩選因子控制簇規(guī)模,通過(guò)附屬簇員避免孤立通信節(jié)點(diǎn)產(chǎn)生,利用網(wǎng)關(guān)使簇形戍網(wǎng)狀結(jié)構(gòu),并理論分析了算法的有效性。最后,仿真驗(yàn)證其性能,結(jié)果表明,與其他算法相比,該算法可以減少高動(dòng)態(tài)下簇首更換頻率控制成簇?cái)?shù)量,增強(qiáng)簇抗毀性,有效地提高了簇的整體穩(wěn)定性,更適合應(yīng)用在軍事航空領(lǐng)域。關(guān)鍵詞:航空自組網(wǎng);軍事航空;分簇算法;備份簇首;附屬簇員中圖分類(lèi)號(hào):TP93文獻(xiàn)標(biāo)志碼:A文章編號(hào):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種具有時(shí)延感知的分簇算法但沒(méi)有注意延長(zhǎng)網(wǎng)絡(luò)壽命,而0引言且設(shè)定所有節(jié)點(diǎn)數(shù)據(jù)的時(shí)隙寬度相等的條件過(guò)于理想;文獻(xiàn)航空自組網(wǎng)(ANET)是移動(dòng)自組網(wǎng)在航空領(lǐng)域的拓展與[10]在蜂窩結(jié)構(gòu)的基礎(chǔ)上,利用感知位置信息的方法進(jìn)行分應(yīng)用,由于具備自組織自修復(fù)的能力和快速高效組網(wǎng)的優(yōu)簇,但其只適合靜態(tài)網(wǎng)絡(luò);文獻(xiàn)[11)從節(jié)點(diǎn)編號(hào)、節(jié)點(diǎn)度及勢(shì)而特別適合解決軍事航空中飛行環(huán)境惡劣高動(dòng)態(tài)拓?fù)洹⒐蕉鹊冉嵌冗x擇簇首,算法較為簡(jiǎn)單且便于維護(hù)但當(dāng)節(jié)點(diǎn)節(jié)點(diǎn)不穩(wěn)定地面設(shè)施保障困難等問(wèn)題,可為軍航通信發(fā)揮抗移動(dòng)性增強(qiáng)時(shí),節(jié)點(diǎn)簇內(nèi)生存時(shí)間急劇下降僅適用于低速移動(dòng)環(huán)境;文獻(xiàn)[13]通過(guò)估計(jì)節(jié)點(diǎn)速度、引入虛擬中心、預(yù)警簇毀、補(bǔ)盲支持編隊(duì)?wèi)?zhàn)術(shù)協(xié)同等作用,從而大幅提升作戰(zhàn)平臺(tái)的頭失效分頻通信等方法設(shè)計(jì)了適合中高速環(huán)境下的分簇算戰(zhàn)術(shù)效能2,因此國(guó)內(nèi)外許多項(xiàng)目及單位對(duì)其進(jìn)行研究如法,但如果節(jié)點(diǎn)數(shù)量較大或不穩(wěn)定時(shí),容易造成頻段空白頻譜美國(guó)的TN歐盟的 NEWSKY項(xiàng)目,以及國(guó)內(nèi)的空軍工程、北資源枯竭的情況;文獻(xiàn)[14]運(yùn)用層次分析法對(duì)篪首進(jìn)行選擇京航空航天大學(xué)等單位形成一種空間信息網(wǎng)成簇方法,不過(guò)其剩余能量、功率水平等不過(guò)ANET使路由協(xié)議、Q0s保障“及可擴(kuò)展性等面參數(shù)不適合軍機(jī):文獻(xiàn)[5].用設(shè)立意愿因子方法選舉簇首臨新的困難。為解決這些問(wèn)題研究人員提出將網(wǎng)絡(luò)劃分提出了適合高動(dòng)態(tài)移動(dòng)網(wǎng)絡(luò)的自適應(yīng)穩(wěn)定分簇算法但該方法成組的方法即分簇算法采用分簇的結(jié)構(gòu)可以很大程度地解沒(méi)有考慮軍用飛機(jī)被擊落等突發(fā)情況對(duì)簇結(jié)構(gòu)穩(wěn)定性的影響決擴(kuò)展性差等問(wèn)題,從而提高網(wǎng)絡(luò)的性能和效率雖然目前對(duì)分簇算法的研究較深入,但其設(shè)計(jì)目標(biāo)需滿足現(xiàn)已有最小、最大連通度等多種較為成熟的分簇算特定的要求并適用于相應(yīng)的環(huán)境而軍事航空自組網(wǎng)具有以下法,它們從權(quán)值設(shè)定地理位置能量大小等多個(gè)角度對(duì)簇的建不同于一般自組網(wǎng)的特點(diǎn):立進(jìn)行研究。文獻(xiàn)[8]為增加網(wǎng)絡(luò)生存時(shí)間基于節(jié)點(diǎn)連接度a)分布場(chǎng)景大尺度和不確定性。飛機(jī)廣泛分布在大洋、采用自適應(yīng)調(diào)節(jié)通信范圍等方法減少能量損耗;文獻(xiàn)[9]提出沙漠等無(wú)地面中轉(zhuǎn)站的區(qū)域。收稿日期:2014-03-02;修回日期:201404-28基金項(xiàng)目:全軍軍事學(xué)研究生課題作者簡(jiǎn)介:代家銘(1989-),男,黑龍江佳木斯人,助理工程師,主要研究方向?yàn)樾畔踩?djm198805@163.com);宋玉龍(1988-),男,黑龍江大慶人,碩士研究生,主要研究方向?yàn)闊o(wú)線通信;尚亞黎(1974-),女,高級(jí)工程師,碩士,主要研究方向?yàn)樾畔步?李冬濤(1978-),男,工程師,碩士主要研究方向?yàn)樾畔踩?羅長(zhǎng)遠(yuǎn)(1973-),男,副教授,博士,主要研究方向?yàn)闊o(wú)線通信1194·計(jì)算機(jī)應(yīng)用研究第32卷b)運(yùn)動(dòng)階段性。飛機(jī)在巡航作戰(zhàn)等不同階段的運(yùn)動(dòng)方首直接通信的未入簇節(jié)點(diǎn)。式、飛機(jī)相對(duì)位置等均存在很大的差異。附屬簇員具有一定的靈活性,其可通過(guò)簇員與別的節(jié)點(diǎn)進(jìn)c)拓?fù)涞母邉?dòng)態(tài)性。飛機(jī)的速度可達(dá)3.5Mach,節(jié)點(diǎn)高行通信,從而避免了孤立通信節(jié)點(diǎn)的產(chǎn)生。如圖1中,單跳簇速移動(dòng)會(huì)造成網(wǎng)絡(luò)拓?fù)淇焖僮兓?直接影響到MAC協(xié)議、路由的附屬節(jié)點(diǎn)9可通過(guò)簇員8與其他節(jié)點(diǎn)通信。另外,由于其只協(xié)議等方面性能。與簇員通信而不參與簇內(nèi)的信息交互所以不會(huì)增加簇的額外d)節(jié)點(diǎn)分布不規(guī)則。由于作戰(zhàn)任務(wù)的差異,導(dǎo)致不同空開(kāi)銷(xiāo)減少了簇首的負(fù)載同時(shí),可以使簇首與簇員達(dá)到負(fù)載域飛機(jī)數(shù)量、密度等相差較大均衡。e)不可預(yù)測(cè)性。在空戰(zhàn)中飛機(jī)存在時(shí)刻被擊落的可能,定義3備份簇首。通過(guò)一定規(guī)則篩選得到且有潛力成地面中轉(zhuǎn)站等同樣面臨被銷(xiāo)毀的危險(xiǎn)另外,在作戰(zhàn)區(qū)域內(nèi)飛為簇首的節(jié)點(diǎn)行軌跡等也存在不可預(yù)測(cè)性。備份簇首在簇首未失效前充當(dāng)簇員的角色,一旦簇首由于f)節(jié)點(diǎn)能量不受限?？諔?zhàn)持續(xù)時(shí)間通常為幾個(gè)小時(shí),軍機(jī)被擊落等原因不能維護(hù)簇的正常通信時(shí),為避免因簇首失效產(chǎn)會(huì)提供足夠的用于通信的能量,因此,不需要考慮節(jié)點(diǎn)通信能生的簇動(dòng)蕩,此時(shí)備份簇首自動(dòng)成為初始簇首并具有簇首的功量耗竭的情況能,從而保障了簇的穩(wěn)定性。通過(guò)以上分析如果不結(jié)合軍事航空自組網(wǎng)的特性而建立定義4簇容量N。簇保持最佳狀態(tài)時(shí)簇員的數(shù)量。的分簇算法,可能會(huì)造成不必要的開(kāi)銷(xiāo)和資源的浪費(fèi),甚至使當(dāng)網(wǎng)絡(luò)中具有一定數(shù)量的節(jié)點(diǎn)時(shí)如果簇的簇員數(shù)量過(guò)通信中斷。本文以軍機(jī)為研究對(duì)象通過(guò)收集節(jié)點(diǎn)地理位置信小,則簇首的簇間開(kāi)銷(xiāo)會(huì)因簇?cái)?shù)量過(guò)多而很大;反之,則會(huì)造成息,計(jì)算理想簇首節(jié)點(diǎn)據(jù)此選取穩(wěn)定性優(yōu)先的備份簇首以避簇內(nèi)簇首負(fù)載很大免簇的振蕩,在單跳簇的基礎(chǔ)上,運(yùn)用簇容量控制簇的規(guī)模,利定義5簇首閾值6。判斷節(jié)點(diǎn)成為簇首的最低標(biāo)準(zhǔn)。用附屬簇員減少孤立通信節(jié)點(diǎn)產(chǎn)生,建立一種適合軍事航空自組網(wǎng)的分簇算法。最后,對(duì)各種指標(biāo)進(jìn)行仿真驗(yàn)證。簇首閾值可增加簇的穩(wěn)定性及減少簇首的更換次數(shù),其設(shè)定須考慮簇的規(guī)模、相對(duì)運(yùn)動(dòng)等因素?；径x2初始簇的建立相關(guān)假設(shè)定義6初始簇。節(jié)點(diǎn)在簇更新前形成的簇。為方便研究提出以下合理假設(shè):由于軍機(jī)在執(zhí)行巡航等任務(wù)時(shí),通常以一定的編制為單a)所有飛機(jī)均為同質(zhì)飛機(jī)(性能相同)且均有唯一的I位,如飛機(jī)中隊(duì)等同一編制內(nèi)飛機(jī)數(shù)量往往在10架以內(nèi)并且標(biāo)志記為ID1,ID2,…,ID。根據(jù)定位系統(tǒng)或者其他手段可以它們的任務(wù)相同或相似。因此,飛機(jī)間的相對(duì)速度、相對(duì)位置獲得自身的地理位置信息M1,M2,…,M,其中,M由位置坐較為穩(wěn)定故可將其默認(rèn)為同一個(gè)簇。另外同一編制內(nèi)的飛標(biāo)和速度矢量組成機(jī)之間(如長(zhǎng)機(jī)和僚機(jī))存在著指揮關(guān)系,并且長(zhǎng)機(jī)的飛行位b)飛機(jī)間通過(guò)公共信道進(jìn)行分簇而分簇后則使用不同置常位于機(jī)群的中心且與僚機(jī)的通信量相對(duì)較多所以可令長(zhǎng)信道通信機(jī)為最開(kāi)始的初始簇首,僚機(jī)成為簇員,簇首建立簇的成員列c)由于飛機(jī)飛行高度的變化通常為幾千米而飛行通信表從而完成簇的初始化工作。由于此過(guò)程飛機(jī)間相對(duì)位置較半徑為幾百千米故忽略飛機(jī)飛行的高度變化。為穩(wěn)定只需要交換成簇信息便可進(jìn)行分簇因此,不作為本文1.2相關(guān)定義研究重點(diǎn)。定義1單跳簇。簇首到所有簇員的距離為一跳的簇。3算法描述單跳簇的任意兩簇員之間的最大距離為兩跳。同理如果簇首到所有簇員的距離為多跳時(shí),則該簇為多跳簇。在圖13.1備份簇首的選舉中,實(shí)線內(nèi)的簇為單跳簇,虛線為兩跳簇。當(dāng)簇跳數(shù)較多時(shí),其初始簇中的初始簇首s向其鄰節(jié)點(diǎn)發(fā)送廣播信息,并通過(guò)內(nèi)的簇員數(shù)量也會(huì)增大。例如,當(dāng)軍機(jī)的通信半徑為300km,收集應(yīng)答信息建立鄰居表;隨后,根據(jù)鄰居表里的位速信息計(jì)若形成3跳簇,其簇的半徑便可達(dá)到900km,此時(shí),簇會(huì)覆蓋算理想節(jié)點(diǎn)及包括s在內(nèi)的所有節(jié)點(diǎn)的備份簇首選擇因子據(jù)作戰(zhàn)區(qū)域內(nèi)的絕大部分飛機(jī)簇內(nèi)開(kāi)銷(xiāo)急劇增大進(jìn)而便失去分此尋找備份簇首。簇的意義。令5的初始位速信息為M,=[(x,y,),(,,)],當(dāng)s收到n個(gè)鄰節(jié)點(diǎn)的位速信息M1=[(x1,y1),("x),"tu,)],,M,=[(x,,),(v,,)]后可以計(jì)算出理想節(jié)點(diǎn)o的位速信息M。=[(x,y,),(vm,),o,)],具體計(jì)算為①首M,=rx+、"一,”)](1)由式(1)可知,理想節(jié)點(diǎn)o的地理位置為所有鄰節(jié)點(diǎn)的中心,其速度反映了所有鄰節(jié)點(diǎn)的整體運(yùn)動(dòng)趨勢(shì)圖1單雙跳簇示意圖為保證簇的穩(wěn)定,所選取的備份簇首應(yīng)與簇的整體運(yùn)動(dòng)趨勢(shì)相吻合且最好位于簇的中心。由于各節(jié)點(diǎn)為同質(zhì)節(jié)點(diǎn),那么定義2附屬簇員?？膳c簇員直接通信但不可與該簇簇備份簇首的選擇便取決于節(jié)點(diǎn)的位置和運(yùn)動(dòng),因此,備份簇首第4期代家銘,等:高動(dòng)態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計(jì)1195·選擇指標(biāo),需要結(jié)合節(jié)點(diǎn)的位置和運(yùn)動(dòng)兩方面因素。均運(yùn)動(dòng)因子,結(jié)合式(8)所得的值即為簇首閾值,即1)位置因子定義7若兩節(jié)點(diǎn)間的距離在一跳范圍內(nèi),則兩者互為鄰(9)節(jié)點(diǎn)3.2簇員的篩選定義8符號(hào) degreel(i)表示節(jié)點(diǎn)i的度,其數(shù)值等于i跳距離內(nèi)鄰節(jié)點(diǎn)的數(shù)量。當(dāng)某節(jié)點(diǎn)成為簇首后,若其簇員超過(guò)簇容量時(shí),則需要通節(jié)點(diǎn)的度可以衡量其在簇中的位置及與其他節(jié)點(diǎn)的連通過(guò)簇員篩選因子對(duì)節(jié)點(diǎn)是否可成為簇員進(jìn)行判斷和篩選。若狀況某節(jié)點(diǎn)的度越大其位置越靠近中心),即更適合成為保持現(xiàn)有速度,節(jié)點(diǎn)間且能通信的保持時(shí)間可反映其穩(wěn)定程備份簇首。因此,將位置因子定義為節(jié)點(diǎn)度的大小。度,于是,將鄰節(jié)點(diǎn)通信保持時(shí)間作為簇員篩選因子v。若初始簇首的鄰節(jié)點(diǎn)較多,當(dāng)計(jì)算每個(gè)節(jié)點(diǎn)的度時(shí),其計(jì)不妨令a為簇首,任取飛機(jī)i,則其簇員篩選因子為y。算量較大,而通過(guò)理想節(jié)點(diǎn)的計(jì)算公式可知,度較大的節(jié)點(diǎn)距由圖3可知下式成立離理想節(jié)點(diǎn)較近,所以初始簇首s可在距離理想節(jié)點(diǎn)R2的圓(ay+b)2+(cy+d)2=R2形范圍內(nèi)尋找備份簇首。)R2-(ad-b)2設(shè)某節(jié)點(diǎn)i的m個(gè)鄰節(jié)點(diǎn)組成的集合為Mi],其可用一其中:0=U(,b=x一x,=,-(m,d=y.-y。個(gè)1×的鄰接矩陣A=[a]1來(lái)表示,元素a關(guān)系式為10