无线Ad Hoc网络MCDS的贪心分布式近似算法

在无线Ad Hoc网络中基于最小连通支配集(MCDS)构建虚拟主干网可以有效缓解广播风暴,提高网络性能,延长网络生存时间.利用单位圆盘图中极大独立集的性质,使用2阶段贪心分布式近似算法构造了MCDS.从理论上分析了算法的时间复杂度、信息复杂度和近似比.

无线Ad hoc网络中虚拟骨干网的模型和设计

利用网络图论中支配集的概念,给出无线Adhoc网络中虚拟骨干网的数学模型。介绍了目前几种常用的虚拟骨干网设计方案,并从算法的复杂度和所需的邻居信息等方面对其进行比较。

无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法

在无线自组织网络中,经常选取一些节点形成虚拟主干网,用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点,虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网,并通过模拟实验评估了算法的性能。近年来,WangFeng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。

近似2-连通k-支配容错虚拟主干网

由于无线网络存在节点失效、链路断裂等特性,虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构,首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度,并证明了该算法的近似比为常数。

一种煤矿井下无线自组网灾后重构算法

矿井事故常导致部分通信链路损坏、通信网络连通性恶化,利用残存节点和有限的新设节点,通过构造局部虚拟骨干网方式重构矿山救援网络可降低网络能量开销,增强连通覆盖控制能力。提出了一种基于多维度虚拟骨干网构造的煤矿井下无线自组网灾后重构算法。考虑无线传感器网络介数中心度、节点紧密度、节点剩余能量筛选机制3个维度,构建了虚拟骨干网节点综合评价指标,选取综合评价指标大的节点作为统治节点,以增强虚拟骨干网的鲁棒性,延长网络寿命。介绍了虚拟骨干网构造过程:在初始阶段,通过多轮选举产生统治节点并更新支配集;在支配集连接阶段,选举出中继节点,各统治节点、中继节点建立连接,形成连通支配集。采用一阶无线电能耗模型分析了虚拟骨干网能耗。采用Matlab R2017A平台对基于该算法重构的网络进行仿真实验,结果表明网络剩余能量、统治节点数量、节点覆盖率等指标均优于采用基于休眠机制和能量均衡的连通支配集算法、能量均衡的最小连通支配集算法构建的网络。

三维无线自组织网络中最小虚拟骨干的近似算法

在均质无线自组织网络中,虚拟骨干(Virtual Backbone,VB)的大小是衡量无线自组织网络质量的一个重要因素,虚拟骨干越小,网络路由开销越少。最小虚拟骨干的求取问题能够抽象为最小连通控制集问题。针对二维无线自组织网络上的单位圆盘图(Unit Disk Graph,UDG)中最小连通控制集问题,目前已有很多研究成果,但是在现实中的某些情况下,单位圆盘图并不能准确地抽象网络。因此,文中提出了在单位球图(Unit Ball Graph,UBG)中构建高质量的连通控制集(Connected Dominating Set,CDS)的算法ST-CDS,给出了单位球图中独立节点个数的一个优化上界,并进一步利用该优化上界得到连通控制集的性能比。所提算法主要运用构造最小斯坦纳节点的斯坦纳树(Steiner Tree with Minimum Number of Steiner Nodes)方法来优化节点之间的连通部分。理论分析表明,ST-CDS算法的性能比为11.8080+ln11,是目前已知该方向研究中最好的结果。仿真结果也验证了ST-CDS算法的可行性。

基于拓扑控制的井下应急通信系统优化部署

在基于自组网的井下应急通信系统中,运用基于拓扑控制的节点部署算法,可以增强网络可靠性,提高通信效率,避免通信盲区。提出应用极小支配集算法求得网络虚拟骨干点作为网关节点,对网络拓扑进行优化,得出井下应急通信系统节点的优化部署。经过对井下拓扑图的计算,网关节点数量与总节点数相比减少了54.55%,节点平均度提高了17%,有效降低路由搜索空间,提高路由效率。