无人机自组网的动态双簇首分簇算法研究.pdf

第卷 第期 年 月沈 阳 理 工 大 学 学 报 收稿日期:基金项目:辽宁省教育厅科学研究经费项目(面上项目)()作者简介:范淼()男硕士研究生通信作者:谭小波()男副教授博士研究方向为无线传感器网络文章编号:()无人机自组网的动态双簇首分簇算法研究范 淼谭小波徐 琪(沈阳理工大学 信息科学与工程学院沈阳)摘 要:无人机自组织网络的动态拓扑特性给分簇路由协议的设计带来一定的挑战如何建立有效稳定的分簇机制至关重要 针对局部网络中弹性的无人机自组网单一分簇算法分簇不合理以及单簇首结构抗毁性低的问题根据局部节点间链路过期时间生成的拓扑结构设计动态双簇首的分簇算法 该算法允许在不同的局部网络形成不同的网络结构同时双簇首设计保证了簇结构的高抗毁性关 键 词:无人机自组网路由协议分簇算法动态双簇首中图分类号:.文献标志码:./.():.:近年来随着无人机技术研究的不断深入无人机在军事场景和民用领域的应用越来越广泛比如情报侦查与监测、精准农业播种、灾害的预测与管理、环境状况监测、空中临时基站、国土安全、互联网交互、运输货物和建筑监督等 无人机受到自身电量、飞行能力以及载荷等硬件因素的限制通常难以完成复杂的工作任务因此弹性的无人机集群协同作业成为趋势由于无人机工作时自身的高移动性、位置分布不均匀等不确定的因素无人机集群有时会遇到通信中断、节点失效等紧急情况 因此面对未来各种恶劣环境条件和复杂的应用需求确保在复杂、变化的环境中能够迅速完成组网和保证良好的通信合理的分簇算法和高抗毁性的路由协议是研究的关键 无人机自组网是一种临时多跳无中心的自组织网络不依赖于地面控制站或卫星等基础通信设施而是将无人机作为网络节点各节点间能够相互转发指令交换感知态势、健康情况和情报数据等 常用分簇算法有基于身份()认证的分簇算法、基于连接度的分簇算法和基于节点权重启发式的分簇算法和链 路 分 簇 算 法()等 但是现有的分簇算法在面对频繁的网络拓扑变化、节点快速移动等极端情况下并不能保证较好的网络性能网络的通信能力略显不足网络的抗毁性差 本文针对单簇首抗毁性低的问题提出双簇首的结构设计动态双簇首()分簇算法以使网络形成更为合理、有效的拓扑结构 动态分簇算法设计.动态分簇算法的提出针对前文提到的传统分簇算法单簇首抗毁性不足和不能合理分簇的问题本文设计双簇首结构提高抗毁性使用动态分簇算法进行合理分簇传统分簇算法的改进方向是减少孤立节点的产生而动态分簇算法的设计原则是只要满足分簇条件就会产生孤立节点对于整个网络来说按照动态分簇的原则部分节点采用分簇结构没有选择分簇的孤立节点采用平面结构 对于某个局部网络是否分簇是通过比对同一个局部网络分簇结构与平面结构下相同属性的优劣程度来决定由基于链路过期时间的网络拓扑图分别计算以发起分簇选择的节点为中心的星型网络结构和拓扑图最大生成树结构当该星型网络的边集与最大生成树的边集重叠度满足 值即网络节点分簇比例时说明星型网络的部分结构属于该局部网络的最优通信结构选择分簇 如果重叠度不满足 值则不选择分簇网络不再进行后续的分簇操作.算法在无人机自组网中节点的高移动性会导致节点间链路不稳定和通信时间过短的问题选取的路由链路过期时间越短路由的可靠性和有效性越低 所以在动态分簇的决策阶段采用以节点间的边为优先选取原则的 算法算法描述如下)通过计算节点间的链路过期时间、节点的位置与移动信息得出局部网络的拓扑图其中顶点即无人机自组网节点集合为 边集合为 权值为边所连接的两节点的链路过期时间)设 其中 是目标最大生成树的顶点集是目标最大生成树的边集为发起 算法的节点集为 邻居节点集)重复下列操作直到 在集合 中选取权值最大的边 其中 且 如果存在多条满足前述条件即具有相同权值的边则任取其中之一将 加入集合 中将 边加入集合 中)输出顶点集、边集.链路过期时间为后续给动态拓扑图的边赋值需要计算两节点间链路过期时间即计算节点间剩余的有效通信时间 原理如图 所示 假设存在节点 与 在初始时间处于通信范围之内链路过期时间后两节点相距最长通信距离则有()()()()()()()沈 阳 理 工 大 学 学 报 第 卷 ()()()()()()()式中:()、()为节点 与 的坐标为节点通信范围为节点 与 在 轴方向的通信范围为节点 与 在 轴方向的通信范围 为节点间剩余的有效通信时间、为节点 与 在 轴方向移动的速度、为节点 与 在 轴方向移动的速度、为节点 与 之间分别在 与 轴方向上的速度图 计算.动态分簇算法描述)网络初始化无人机节点 通过 获得其节点信息包括节点坐标 和、节点的速度信息 和 规定以东和北方向为 轴与 轴移动的正方向)网络各个节点广播自己的节点信息)当节点收到邻居广播的信息后计算出与邻居节点剩余有效通信时间 设 为最小通信时间阈值其中 的节点向邻居节点中 最大的节点 发送自己的邻居表信息)当节点 接收到邻居节点 发送的邻居表信息先对局部网络成簇或不成簇进行最优选择的计算如果收到多个邻居节点的邻居表信息只计算最先收到的信息 取两节点邻居集的交集加上发送与接受信息的两节点得出局部网络拓扑图拓扑图中两节点之间存在边代表连接边的两个节点处于通信范围之内边的权值为两节点最长链路过期时间 通过该拓扑图计算两个生成树其中生成树 为局部网络拓扑图最大生成树采用 算法生成且初始生成树子集包含发送与接收邻居表的两节点生成树 为以发起分簇选择的节点为中心的星型网络结构以进行分簇计算的节点从邻居表接收节点向剩余节点取边集最后得到边集 和 若两边集满足()即满足网络节点分簇比例 则进行分簇向周边节点发送成簇信息 节点 和 中节点度大的一个成为副簇首另一个成为主簇首否则选择不成簇将节点设置为孤立节点)当孤立节点收到多个成簇信息时选取 最大的节点返回确认成簇信息 当簇首节点收到成簇通知时优先以收到的簇为准)当节点在一定时间内没有收到任何成簇通知则成为孤立节点孤立节点从结构上同时兼职主副簇首形成簇节点数只有一个的特殊簇运行纯平面路由协议 簇结构的维护机制.簇信息的维护和优化在双簇首结构中主簇首负责簇内节点间的通信副簇首负责簇间节点的通信双簇首都需要定期广播报文以维护簇内节点以及邻居节点信息簇的维护机制如图 所示图 簇的维护机制 对于双簇首结构只有当簇内的某个节点同第 期 范 淼等:无人机自组网的动态双簇首分簇算法研究时处于两个簇首的通信范围内时认为该节点存在该簇内 同时为保证双簇首的抗毁机制双簇首需要高频消息交互维持联系 所以节点没必要同时对两个簇首都进行回复 如果节点在接收时间限制内可以收到双簇首的广播簇维护消息则只需要对主簇首进行回复即可以维护簇结构并将标记位设置为 报文级别设置为一级如果没有收到另一个簇首的消息则对发送方进行正常的路由回复优化后的簇维护机制如图 所示 当主簇首收到标记位为 的节点的回复报文时将节点加到簇信息表中主簇首定期与副簇首通信时发送该表副簇首通过接收主簇首发送的簇信息表维护簇内节点信息图 优化后的双簇首簇维护机制.节点的加入当一个孤立节点收到两个簇首的广播时分别计算与双簇首的链路过期时间 如果两个时间中较短值依然大于入簇时间阈值该节点对主簇首发送路由回复消息标记位设置为 即可加入簇主簇首收到标记位为 的回复消息时将节点信息加入到簇表并发送给副簇首 如果是簇首节点移动到另外的双簇首的通信范围内并且计算与双簇首的最长链路过期时间均大于与自身簇的另一个簇首的链路过期时间则选择解散该簇首节点所在的簇并且加入新的簇.节点的离开在无人机自组网中节点位置是会改变的当簇内节点收到额外的双簇首的广播信息时将其信息加入备用簇信息 当节点不能收到原双簇首的簇维护消息时或者收到簇首发送的簇解散消息则代表节点不属于原簇 此时如果节点保存了备用的簇信息则直接向备用簇的主簇首返回入簇消息加入备用的簇如果节点没有保存备用的簇则代表此时节点并不处于任何一个簇的双簇首的通信范围不能采用簇的通信机制节点将自己的簇属性重置并设置自身为孤立节点.簇的毁伤检测与重组在普通的单簇首结构中维护簇的功能主要在簇首节点上单簇首通过频繁的广播信息让簇内节点和骨干网络中的邻居簇首获取簇首信息因节点对该簇首的感知只能来自簇首本身的广播信息当出现簇内节点接收不到簇首的广播信息时不能判断原因在动态分簇阶段可以成为双簇首的两个节点必定是在局部网络中链路过期时间最长的两个节点而当双簇首都离开有效通信范围时代表该簇已经到达了不稳定的时候簇内其他节点也不足够稳定此时没有必要继续维持该簇 当双簇首收到了毁伤的消息时双簇首广播簇解散消息以解散该簇并将自己设置为孤立节点 毁伤检测机制如图 所示图 毁伤检测机制 当没有节点可以同时收到两个簇首的毁伤检测消息时可能因为某个簇首已经受到来自外部的攻击无法广播毁伤检测也可能是因为短时间移动距离过大在双簇首的通信范围交集内不存在节点 当簇首节点在一定时间内只能接收到毁伤消息则证明另一个簇首因为高移动性或者外部毁伤而离开通信范围如果簇首因为自己的高移动性离开了原始的簇其原因多出于临时状况或者因为受到攻击导致丧失性能此种由于节点本身原因而导致簇首结构的解散对簇本身并没有影响说明簇本身依然具备构成成簇的条件 为保证簇的稳定性以及发挥双簇首高抗毁性的优势进行簇的重组单簇首沈 阳 理 工 大 学 学 报 第 卷变成传统的单簇首结构并进行新的双簇首选举.簇的解散当需要进行簇的解散时如果双簇首仍处在通信状态则解散发起者向另一方簇首发送簇解散请求同时广播簇解散消息 当另一个簇首收到解散请求时停止广播簇维护报文并广播簇解散消息 簇内节点在一定时间内没有收到双簇首的维护消息并且收到簇解散消息则代表该簇已经解散 如果双簇首不在通信范围之内则各自广播簇解散消息收到簇解散消息的节点如果没有备用簇则直接将自己设为孤立节点该簇解散如果双簇首维护的簇内节点少于两个时为了维护簇组织结构需要两个簇首频繁广播维护消息但为了维护少于两个成员的簇而增大两个簇首的维护开销是不合适的说明该簇已没有存在的必要则由主簇首主动发起簇解散直接广播簇解散消息并将节点属性设置为孤立节点 仿真与验证.仿真场景与参数设置采用 平台对提出的动态双簇首分簇算法进行仿真仿真场景的大小设置为 采用随机移动模型 节点通信半径设置为 业务流采用恒定比特率业务()为测试不同变量对分簇算法的影响本文设定节点数量与 值作为变量固定移动速度为/仿真平台配置与参数设置见表 表 仿真平台配置与参数设置名称参数场景大小 节点通信半径 业务流 层协议.节点数量、移动速度/天线类型全向天线队列类型仿真时间.仿真结果分析本文的仿真实验将 算法与传统的 算法相对比以验证 算法的可行性与优越性 对动态分簇算法着重评估算法对网络的划分能力 对比 值分别为.、.、.时的 与 分簇算法考虑分簇算法对网络分簇率()、平均每个簇的节点数量()的影响 仿真结果如图、图 所示图 不同节点数量的 图 不同节点数量的 由图 可见影响 算法分簇率最明显的属性是 值因为 值是直接决定分簇与否的阈值其次随着节点数量的增加分簇率有不同程度的减少因为当节点数量增加拓扑结构中的边也随之增加使星状拓扑较难覆盖最大生成树传统的 算法一直保持极高的分簇率但由图 可见尽管 算法分簇率高但由于是低效分簇传统的 算法对于簇节点的管理不如 动态分簇算法 用更少的簇首管理了更多的节点平均每个簇的节点数量更高分簇更为合理 结论本文设计了动态双簇首分簇算法 可以有效解决局部网络分簇不合理的问第 期 范 淼等:无人机自组网的动态双簇首分簇算法研究题通过动态的分簇可以让无人机自组网在不同的局部网络形成不同的网络结构 双簇首结构可以有效解决单簇首抗毁性不足以及过多的簇首导致路由开销过大的问题 双簇首分别处理簇内与簇间的通信可以有效降低单簇首的负载针对双簇首结构特点设计了相应的簇维护机制优化了簇的维护成本加入了关于毁伤检测的机制增大了簇的抗毁性参考文献:.():.():.:.():.():.:.():.():.():.():.赵嶷飞孟令航李克南.基于人工智能的智慧民用航空运输系统.指挥信息系统与技术():.朱建伟袁国辉.基于倾斜摄影测量技术的无人机城市建筑监测系统在违建查找中的应用.工程勘察():.张哲吴剑何诚等.复杂环境下多目标多无人机协同任务规划.兵器装备工程学报():.:.():.():.麦晓明王锐陈海涵等.输电线路无人机巡检数据链路通信系统设计.广东电力():.罗冠辰于剑桥张思宇等.穿越恶劣天气区域的无人机航迹规划.北京理工大学学报():.赵洪岩谭小波徐飞.:一种面向 网络的路由协议.沈阳理工大学学报():.(责任编辑:和晓军)沈 阳 理 工 大 学 学 报 第 卷