基于ADS-B报文的航空自组网分簇算法

a Communication and Network基于ADS-B报文的航空自组网分簇算法张海',李纲,陈广晓2,李静林2(1.空军装备研究院雷达与电子对抗研究所,北京100876;2.北京邮电大学网络与交换技术国家重点实验室,北京100876)摘要∶在大规模Ad-loc网络中,有效的层次架构是实现路由和资源管理的关键技术。针对航空网络中因飞机数量增加、网络规模増大而导致网络中飞机通信质量下降的问题,提出了一种基于ADS-B报文的航空Ad-Hoc网络分簇算法。该算法利用ADS-B报文提供的飞机速度、位置信息、连同节点度,进行簇的形成和维护。设计了大量的仿真实验,结果表明该算法可以减少簇的个数和节点切换率,从而有效提高了簇的稳定性和航空通信的效率。关键词:航空电信网;ADS-B;Ad-Hoc;分簇算法中图分类号:TM929.5文献标识码:A文章编号:0258-7998(2013)07-0089-04An ADS-B based clustering algorithm in aviation Ad-Hoc networksLi jinglin(1. Radar and EW Institute, Equipment Academy of Air Force, Beijing 100876,China2. Beijing University of Posts and Telecommunications, State Key Laboratory of Networking andSwitching Technology, Beijing 100876, ChinaAbstract: An effective architecture is the key technology of routing and resource managing in large Ad-Hoc networks. In theaviation network, the quality of communication between aircrafts declines with the increasing number of aircrafts.Todeal with thisproblem, an ADS-B message based novel clustering algorithm is presented for aviation Ad-Hoc networks. The piuses the mobility and location of aircraft, provided by ADS-B messages and node degree for cluster formation and maintenanceSome simulations are performed and the results indicate that the proposed algorithm can lower the number of clusters and the rateof switching nodes, and it can effectively improve the cluster stability and efficiency of aeronautical communicationsKey words: aeronautical telecommunication network: ADS-B: Ad-Hoc: clusterADS-B技术是未来航空监视的主要手段之一,它点竞争有限的无线信道,增加了发生碰撞的概率。为减以地空/空空数据链为通信手段,以导航系统及其他机少共享相冋信道的节点数目、降低碰撞概率、提高信道载设备产生的信息为数据源,由具有ADS-B功能的飞利用率须对移动节点进行分簇14,以提高通信质量。机将自身的位置、速度等SV( State Vector)信息周期性对本文提出了一种基于ADS-B报文,综合移动性、位外广播,地面站和其他飞机接收这些报文,进行飞机间置、节点度特点,采用权值进行评估的分簇算法的通信和监控。图1为航空Ad-Hoc网,簇内飞机可直接通信,簇间随着飞机性能和数量的提高,ADS-B应用不断升级,飞机通过网关通信,相隔太远的簇对其覆盖范围有了更高要求。移动自组网(Ad-Hoc)技术能通信,为增强信道利用率,通过簇头将信息转发给基站有效解决这一问题。Ad-Hoc是一种自组织的无线多跳网,1传统分簇算法组网无需固定路由器,所有节点均移动,并能以任意方式目前存在很多分簇算法,算法直接影响簇的稳定动态地与其他节点保持联系。在航空Ad-Hoc网络中,由性、大小以及节点担任簇头的时间,从而影响生成簇和于数据链覆盖范围有限导致两个无法通信的飞机可借助维护簇所需开销12-51。其他节点转发进行通信,扩大了ADS-B的覆盖范围最大连接度算法1尽可能减少了路由器的数目。其由于Ad-Hoc采用共享无线信道方式工作,过多节思想是,节点间通过交换控制信息得到邻居节点的数《电子技术应用》2013年第39卷第7期通信与网络Communication and NetworkO簇成员关系。此时,已在一个簇中的节点可能离开所在的簇加簇头入别的簇,而簇头可能进入别的簇头的范围或被毁,簇⊙网关节点维护是对初始簇形成后上述事件的补救。下面将描述所提出的成簇算法,包括成簇采用的度1簇范围量、成簇算法和簇维护。2.1簇的度量权值 weight的定义分簇算法要求簇能很好地适应网络拓扑的动态变化,在航空网络中,由于飞机高速移动,移动方向不定08地选择族头防止选择边缘节点作为族头造成的不稳飞机的移动性对簇的稳定性有很大影响。同时位置信息反映邻居节点间的距离,通过位置信息和节点度能很好定。因此,本文提出一种基于多种因素的权值计算方法,权值为weight=axk x mobility +6 xwxdegree+cxrxdistance (1)图1航空Ad-Hoc网其中,a,b,c是权值因子,a+b+c=1,据不同应用场景,设目,该节点和其邻居节点中具有最大度的被选为簇头,置3个因子的值;k,,r是常数因子,需保证3个影响因度数相同时,选D最小的作为簇头,簇头的一跳邻居节素最后计算时在同一量级上,提高wit精度点为该簇普通成员。其优点是簇数目较少,减少分组投mobility为飞机相对移动性度量,节点从ADs-B报递时延,但信道空间重用率较低。文中提取速度和位置信息,采用LET计算两节点的相最低移动性算法2-3尽量保持了簇结构的稳定性,其对移动性思想是节点的移动性越高,其权重越低,选最高权重的LET=-(ab+cd)+va+e2)r-(ad-bc 2(2)节点作为簇头。该算法需要一种机制来量化节点的移动性,简单的方法是通过节点间相对速度绝对值的时间平a=vcos -v cos0均来衡量节点的相对移动性。基于地理位置的算法2-是按地理区域划分簇结构,c=vine -v sino使地理位置上较靠近的节点组成簇。其思想是节点通过交互位置信息确定本地的网络拓扑,然后依据邻居节点其中是两个节点,为其传输范围,速度为v和n,的分布来选择簇头并形成簇。此方法可减少簇头和簇内方向角为θ和θ,坐标为(x,y)和(x,y)。通过LET计算两节点间通信的总功率和平均传输时延,但并非所有节点节点间链路的持续时间,反映两节点的相对移动性,间都可获得节点位置信息。接反映两节点相对速度,如:两节点距离很近,但相对速以上算法往往只考虑系统中节点的某一特性,应用度很小,ET会很大;反之,两节点距离很远,但相对速场合受限,簇的性能较差。由于飞机高速移动和方向不度很大,LET会很小。因此,LET越大,说明两节点的相定,不能只考虑某一因素。飞机周期性发送ADS-B报文对移动性很小;反之则说明两节点的相对移动性很大。设其携带飞机SV信息,因此,本文提出一种基于ADS- B mobil" LEr°报文的分簇算法,将以上几种传统算法进行加权来进行成簇和簇维护。为节点的节点度与理想度间差值的绝对值2基于ADS-B报文的分簇算法即 Degree=ld-Dl,d和Dd分别为节点的当前节点度在成簇算法中,由于网络拓扑动态变化1,需维护节和理想节点度,选择理想节点度的目的是保持簇大小平衡。由于飞机广播的ADS-B报文只能被传输范围内的点的角色信息,如:簇头、簇成员、孤儿和NUIL。簇成员是簇的基本节点,实现簇内节点的基本通信,属于不同跳邻居节点接收到,因此,形成的为一跳簇,飞机依簇的簇成员,又叫网关节点,用于簇间通信。簇头管理冀据收到邻居节点的ADS-B报文记录自己的度。Distance为节点与邻居节点的平均距离,其越小说明相应的簇和形成(包括接收一个节点作为成员),并掌握与邻居节点传输过程中能量消耗越少,且相对稳定。从其所有簇内成员的信息。孤儿节点是一个独立节点,不ADs-B报文中获取飞机位置信息,计算邻居节点间的属于任何簇。在初始成簇之前,所有节点都处于NULL平均距离状态,需进行成簇过程。当节点不处于NULL状态时,进行簇维护V(x1+x)2+(0y-y)初始成簇阶段的目的是选簇头,并初始化簇的成员Distance=-4=(3欢迎网上投稿www.chinanet.com《电子技术应用》2013年第39卷第7期Communication and Network根据权值分簇算法的策略需要,移动节点需维护一2.3簇维护些信息,用来完成链路保持、簇头选择及簇的更新维护在Ad-Hoc网络中,节点移动造成拓扑頻繁改变,簇工作。此算法中,每个节点需维护两个表:自身信息表维护的目的是维持拓扑和簇的稳定,包括节点管理和簇(见表1)和邻居节点信息表(见表2)管理表1节点信息表2.3.1节点管理(1)节点加入节点ID标识节点的唯一性节点加入存在两种情况,即孤儿节点和新节节点状态NULL、簇头、簇成员、孤儿节点节点所在簇头簇成员标识自己的簇头,簇头即为自己的ID点的产生(如某一节点刚开机);分簇后,不属于任记录节点收到簇头或簇头收到成员节点的时间一簇的节点被标识为孤儿节点。孤儿节点和新开时间戳簇大小节点所在簇拥有的成员数(对网关节点和簇头很有用)机节点均随ADS-B报文周期性向邻居广播加入节点度与自己相关的节点度(对于簇头而言,节点度即簇大小)信息 Join_request,携带自己的ID和状态(孤儿或理想节点度据网络中的拓扑进行初始化NUL),邻居簇头收到 Join_request和ADS-B信息平均移动性与所有邻居节点相对移动性的平均值后,据ADS-B判断此节点是否符合条件(通过移动平均距离与所有邻居节点距离的平均值性、位置判断),若判断为满足加入,簇头需检查自权值 weightW。= axkxM+b×u×D+ cxrxDS已的度的门限值(与理想度相差不能大于某一值或表2邻居节点信息表等于理想节点度的2倍)判断是否接受新节点:如邻居节点ID从 HELLO消息或ADS-B消息获取果能则向请求节点发送确认加人信息 Join_response,携邻居节点状态从 HELLO消息获取带自身基本信息,请求节点收到 Join_response后修改状邻居节点簇头ID从HELO消息获取,若是孤儿节点态为簇成员,并向周围广播簇成员信息;若不符合条件,则节点簇头为0则簇头不做响应;若节点发出 Join_request超出门限时间邻居节点权值从 HELLO消息获取(用于选择簇头)后未收到 Join_response,则认为自己不能加入任何簇,更新状态为孤儿节点。2.2成簇算法描述(1)初始化每个节点的信息表和邻居节点信息表。节(2)节点移动或消失点开始处于NUIL状态,通过接收邻居节点ADS-B报此处节点采用分步式自动判断自身状态,如果簇成文,与邻居节点交互helo消息,对表进行初始化;通过员一段时间内不能收到簇头的ADS-B消息,则判断自周期性交换ADS-B报文,节点n记录自己的度数d。己已远离此簇,修改状态为孤儿节点;如果簇头一段时间不能收到某个成员的ADS-B消息,则判断此节点已(2)每个节点计算其度数与理想节点度D。之差,即经离开本簇,将节点信息从簇成员表中删除;如果簇头Dn=dl-Dl。(3每个节点通过收到的ADS-B报文计算LE,计算到的新节点的信息数目,则判断已脱离原来簇成为普通自己与邻居节点的相对移动性M。(4)每个节点通过收到的ADS-B报文计算自己与郭节点,设置其状态为孤儿状态,向周围广播 join__request居节点的平均距离DSn。旧成员节点收到簇头 Join_request后,修改自身状态为孤儿节点,向周围广播 Join_request(5)每个节点计算权值W。=a×kxM2+b×xDn+cxr×DS;之后将自身信息组成hell消息随ADS-B报文周期性2.3.2簇管理(1)簇消失:簇头消失或移动为簇消失,解决方法与向邻居节点广播。节点移动的处理方法相同。(6)相邻节点收到helo消息携带的W,后依次进行比较,选其中W。最小的节点为簇头,若W。相同,则选(2)簇合并:每个簇有一个最高节点度(设为理想度ID最小的节点为簇头,成为簇头的节点向周围广播簇的2倍),由于簇头在广播自身信息时携带了自身簇成头消息,携带自身ID、Wn、节点度、簇头状态,宣布自己己员数,处于两簇间的网关节点,根据收到的多个簇的簇成员数进行计算,若合并后簇的成员总数不超过门限成为簇头。(7)邻居节点第一次收到簇头广播的簇消息时,将自值,则通过两个簇头的W选择出新的簇头,向两簇头发身状态由NUL设为簇成员,并广播自身状态,携带自送合并信息,包含自身1,两端簇头D簇头的W、每己和簇头的1D,声明已成为某一簇的成员(一个簇成员个簇的成员数量,簇头收到信息后,向自己的簇成员发送合并信息,其中携带新簇头ID,完成两簇的合并。可同时处于多个簇中,这种成员被标识为网关节点)3性能评估(8)与所有邻居节点不连通,或不能成功加入任一簇为准确刻画算法性能,需用仿真对4种算法进行比的节点被标识为孤儿节点。较。借助NS-2仿真以上算法。在150×150海里的区域(9)重复步骤(2)-(8),直到所有节点状态标识完。内随机放置200架飞机,飞机移动方向在(0,27)内随机《电子技术应用》2013年第39卷第7期91通信与网络 Communication and Netw水k分布,由于救灾场景下低空飞机速度为400km/h-500km/h因此移动速度在400km/h~500km/h间随机选择,飞机间1采用UAT数据链D,仿真时间为5mm主要采用以下衡as- ADSW1HIGHT量指标:簇头数C、单位时间内节点重新加入簇的次数J04(节点移动)。4种算法都采用按需更新策略。--LOWMOBILE通过调整UAT数据链的覆盖范围,查看飞机传输范21B0n4即101围对簇头数的影响,覆盖范围从20~120海里以10递增变化;通过修改权重因子,査看其对算法的影响。仿真结图3节点重新加入簇的次数随数据链传输范围的变化果如图2所示, LOWMOBILE为最低移动性算法,HGHr空网络特性提出了基于权值的成簇算法。该算法利用航为最高节点度算法,GP为基于位置算法,ADSW和至网络中的ADS-B应用,综合考虑移动节点的三个因ADSW为基于ADS-B报文的权值分簇算法。前者,素,适合新航行系统中作战或救灾场景下飞机共同完成deal=10,a=0.7,b=c=0.2;后者, ideal-=7,a=0.4,b=c任务需组建的Ad-Hoc网络。通过仿真结果可见,综合0.3,可比较不同权重因子的ADSW性能。从图2可知考虑各种因素考虑,提高了成簇速度,减少了簇数目,节所有算法中簇头数随数据链覆盖范围的增加而减少,逐点加人新簇的次数趋于平缓,增强了簇的稳定性。适用渐趋于1,当传输范围大于60后,变化速率逐渐降低,于新航行系统中承载ADS-B应用和飞行速度、方向不此结果符合预期,LUAT覆盖范围越大,节点传输范围越定的航空场景大,簇的覆盖越大。此外,还可看出ADSW的簇头数小于参考文蔚其他几种算法,因为ADSW对簇头节点有限制,每个簇1张军.现代空中交通管理M]北京:北京航空航天大学内成员分布较均衡,且ADSW1稍高于ADSW,因为其权出版社,2005重因子b更大。2]郑少仁,王海涛,赵志峰,等,Ad-Hoc网络技术[M]北京:人民邮电出版社,20051003]何献武,基于节点位置和移动性的分群算法[J].四川兵工学报,2011,32(4):60-64.4]雒宝宏,杨瑞娟,马晓岩,等.基于群限制的AdHo网络多跳分群算法!J计算机工程,2008,34(17):120-122数据链传输范围[5]袁晓晶,张军,黄智刚.空基与星基组合监视系统中的图2簇头数随数据链传输范围变化的曲线ADS-B分群算法[J电讯技术,2007,47(1):82-85观察UAT传输范围对节点重新加入簇的次数影响,[6 Su William, LEE S J, GERLA M. Mobility prediction inwireless networks. 0-7803-6521-6/$10.00(C)2000 IEEE.即簇的稳定性,场景配置与以上相同,仿真结果见图3。[71 Fei Huang, Zhang Jun, Zhu Yanbo, Liu wei. Modeling由图3可知,所有算法中节点重新加入簇的次数J随传and simulation of an aeronautical sub network based on输范围的增长而逐渐减小。UAT传输范围较低时,簇数universal access transceiver[C]. 2008 Asia Simulation Con目较多,簇内节点数目少,甚至只有一个簇头,此时节点ference-7 Intl. Conf. on Sys. Simulation and Scientific离开原簇概率很小。当传输范围逐渐增大后,J逐渐增(收稿日期:2012-12-25)加并在传输范围为70海里左右达到最大,随后又开始下降,因为簇覆盖范围增大时,节点移出原簇的概率随作者简介之下降;此外,还可看出,ADSW稳定性高于 ADSWI,因张海,男,1979年生,硕士,工程师,主要研究方向:新为ADSW的权重a更大,飞机的移动速度对于簇的稳定性航行系统,数据链系统。影响较大李纲,男,1974年生,硕士,工程师,主要研究方向:空本文在对已有分簇算法进行分析的基础上,结合航间目标监视技术(上接第88页)with delay-line and non-linear circuit(for ToT)[JI成都:成都理工大学,2008Nuclear Instruments and Methods in Physics Research A[2]王敏数字核能谱测量系统中滤波与成形技术研究[D](2011)S24-S27(收稿日期:2013-03-03)成都:成都理工大学,2012[3]肖无云,魏义祥,艾宪芸.数字化多道脉冲幅度分析中的作者简介梯形成形算法[J清华大学学报(自然科学版),2005,45王敏,女,1975年生,讲师,博士,主要研究方向:核辐(6):810-812射测量技术及核测量仪器研究[4] ORITA T, TAKAHASHI H. A new pulse width signal pro欢迎网上投稿www.chinaaet.com《电子技术应用》2013年第39卷第7期