一种无线自组网主干网优化生成方法

摘要

本发明公开了一种无线自组网主干网优化生成方法，步骤1、构建格局集合X，格局集合X包括集合Z、集合

说明书

技术领域

本发明属于无线通讯领域，涉及无线自组网或物联网的节点管理。具体涉及一种无线自组网主干网优化生成方法，适用于大规模部署的无线自组网，解决如何从扁平对等结构的无线网络中确定关键节点，利用关键节点构成该自组网的主干结构，从而提高网络中数据传输效率，并减少节点能耗。

背景技术

无线自组网通常由多个可移动终端组成，是一种多跳自治网络系统。无线自组结构扁平，其中各节点的地位相等，没有物理主干结构。与传统网络不同，无线自组网中的节点可以与网络中其他任意节点直接进行数据传输。因此，无线自组网相对于传统网络拥有更高的自由度。然而，当网络中部署节点较多时，网络容易出现如下问题：(1)多个节点与同一个节点进行通信时，通信信道数量不足；(2)距离较远的节点间直接进行通信会造成设备消耗大量能源，缩短电池使用寿命，或造成节点能源浪费。

为了规避这些问题，目前常用的手段为将无线自组网抽象为传统网络，再使用传统网络的通信管理方式对数据传输进行管理。具体方法如下：

(1)根据各节点位置，指定各节点仅与相邻的某些节点进行通信。

(2)同时在网络中指定一些节点为服务节点(主干网)。

(3)若需要通信的两节点不相邻，则将数据传送给某个相邻的服务节点，通过服务节点将数据转发至目的节点。

例如图1所示无线自组网，其中每个节点与自己相邻的节点相连，C、D节点为网络主干。若A节点需要与D节点通信，则可以它们可以直接进行数据传输；若A节点需要与其他节点进行通信，则必须通过D节点进行转发。例如，若A与B节点进行通信时，A首先将数据发送给D，D再将数据转发给C，最后C将数据发送给B。

使用这样的策略可以极大节约通信信道使用数量。若允许节点间任意通讯，则每个节点需要至少5个信道(信道数量等于节点个数)。按照图1的处理方式，C、D节点需要三个信道进行通信，其他节点只需要一个信道。同时，此处理方式可以解决远距离传输能耗过大的问题。若A与B的距离足够远，那么AB直接通信的能耗通常大于通过CD节点转发所需能耗的总和。

此处理方式中的难点在于如何确定网络主干。若选择的主干网节点数量过少，可能出现某些节点没有与服务节点相邻，无法与远距离的其他节点通信；若选择的主干网节点数量过多，网络可能仍然有能耗过大或信道不足的问题。为了获取适合适的主干网，通常使用图论算法求解抽象网络中的支配集或支配集变种结构作为主干网。图结构的支配集及其绝大部分变种结构的求解均为NP难问题，目前仍然没有完美的求解算法。

发明内容

本发明所要解决的技术问题是克服现有技术的缺陷，提供一种无线自组网主干网优化生成方法。

为了解决上述技术问题，本发明所采用的技术方案是：

一种无线自组网主干网优化生成方法，包括以下步骤：

步骤1、构建格局集合X，格局集合X包括集合Z、集合

集合Z为集合V的子集，且由集合Z构成的无向图G的子图G(Z)为连通图，

集合

集合

初始状态下，将集合Z初始设置为集合V，集合

步骤2，从集合Z中随机选择一个子图G(Z)的非关键节点，并从集合Z中删除该非关键节点，根据删除非关键节点的集合Z，重新计算集合

步骤3，对格局集合X做变换调整，

步骤4，若变换调整后的格局集合X中的集合

如上所述的步骤3包括以下步骤：

步骤3.1，记已知历史最优格局集合X

步骤3.2，若集合

步骤3.3，迭代次数iter值增加1，

步骤3.4，寻找当前格局集合X的最优的变换操作

步骤3.5，若当前η值为逻辑真且若对当前格局集合X执行最佳的变换操作

若当前η值为逻辑真且当前格局集合X执行最佳的变换操作

若当前下降标记η的值为逻辑假且若对当前格局集合X执行最佳的变换操作

若当前下降标记η的值为逻辑假且对当前格局集合X执行最佳的变换操作

步骤3.6，对当前格局集合X执行最佳的变换操作

步骤3.7，若f(X)

步骤3.8，若当前下降标记η的值为逻辑假，则对于更新后的当前格局集合X中所有集合

步骤3.9，回到步骤3.2。

如上所述的步骤3.4中最优的变换操作

如上所述的节点u

步骤3.4.1，从集合

步骤3.4.2，记节点序列ivs包含集合

步骤3.4.3，对节点序列ivs中每一个节点u′进行δ

步骤3.4.4，根据δ

步骤3.4.5，保留节点序列ivs中前κ个节点，其余节点删除，κ为一小于节点序列ivs长度的设定常数，

步骤3.4.6，令节点u

步骤3.4.7，记节点u

步骤3.4.8，将集合Z中所有节点标记为未访问，

步骤3.4.9，令节点v

步骤3.4.10，若节点v

步骤3.4.11，计算

步骤3.4.12，记节点u

步骤3.4.13，标记集合Z中与节点v

步骤3.4.14，若节点i

步骤3.4.15，当前格局集合X的最优的变换操作为

如上所述的步骤3.4.3、3.4.7、3.4.12中的δ

步骤3.4.3.1，记δ

步骤3.4.3.2，记由集合Z构成的无向图G中节点A的邻居节点为节点q′，遍历所有节点q′，若

如上所述的步骤3.4.11中计算

步骤3.4.11.1，记

步骤3.4.11.2，记由集合Z构成的无向图G中节点v

如上所述的步骤3.6包括以下步骤：

步骤3.6.1，将节点u

步骤3.6.2，根据当前集合Z，重新计算集合

步骤3.6.3，更新变换禁止标记数组tt中u

本发明所生成的连通支配集构成的主干网能够服务网络中的所有节点，且保证主干网的信号传输成本尽量小，能够节约网络中数据传输的总能耗。本发明在无向图中寻找一个最小连通支配集作为无线自组网的主干网络，具体给出了如何求解无向图的最小连通支配集算法。本发明所给出算法计算时间少，目标值更小。

附图说明

图1最小连通支配集的示意图；

图2为变换操作的示意图；swap即为变换操作，即将节点A插入集合Z同时将节点I从集合Z中删除。其中黑色节点为集合Z中的节点，灰色节点为集合

图3为从给定无向图，使用本方法求取最小连通支配集的步骤示例图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。

连通支配集定义：

对于给定无向图G＝{V，E}，若集合D满足以下条件：

由集合D生成的无向图G的子图G(D)为连通图；

集合V中的任意节点必然属于集合D或与集合D中的某个节点相连。

则称集合D为无向图G的一个连通支配集。

一种无线自组网主干网优化生成方法，包括以下步骤：

本方法旨在从给定无向图G寻找节点数目最少的连通支配集。

步骤1，构建格局集合X。格局集合X包括集合Z、集合

集合Z为集合V的子集，且由集合Z构成的无向图G的子图G(Z)为连通图。

集合

集合

初始状态下，将集合Z初始设置为集合V，集合

步骤2，从集合Z中随机选择一个子图G(Z)的非关键节点，并从集合Z中删除该非关键节点。根据删除非关键节点的集合Z，重新计算集合

步骤3，对格局集合X做变换调整。

步骤4，若变换调整后的格局集合X中的集合

步骤3对格局集合X做变换调整包含以下步骤：

步骤3.1，记已知历史最优格局集合X

步骤3.2，若集合

步骤3.3，迭代次数iter值增加1。

步骤3.4，寻找当前格局集合X的最优的变换操作

步骤3.5，若当前η值为逻辑真且若对当前格局集合X执行最佳的变换操作

若当前η值为逻辑真且当前格局集合X执行最佳的变换操作

若当前下降标记η的值为逻辑假且若对当前格局集合X执行最佳的变换操作

若当前下降标记η的值为逻辑假且对当前格局集合X执行最佳的变换操作

步骤3.6，对当前格局集合X执行最佳的变换操作

步骤3.7，若f(X)

步骤3.8，若当前下降标记η的值为逻辑假，则对于更新后的当前格局集合X中所有集合

步骤3.9，回到步骤3.2。

说明：

对当前格局集合X执行变换操作

步骤3.4中寻找当前格局集合X的最优的变换操作

本步骤目的在于寻找能够使得格局集合质量函数f(X)减少最多的最优的变换操作

步骤3.4.1，从集合

步骤3.4.2，记节点序列ivs包含集合

步骤3.4.3，对节点序列ivs中每一个节点u′进行δ

步骤3.4.4，根据δ

步骤3.4.5，保留节点序列ivs中前k个节点，其余节点删除。k为一小于节点序列ivs长度的设定常数。

步骤3.4.6，令节点u

步骤3.4.7，记节点u

步骤3.4.8，将集合Z中所有节点标记为未访问。

步骤3.4.9，令节点v

步骤3.4.10，若节点v

步骤3.4.11，计算

步骤3.4.12，记节点u

步骤3.4.13，标记集合Z中与节点v

步骤3.4.14，若节点u

步骤3.4.15，算法结束，当前格局集合X的最优的变换操作为

步骤3.4.3、3.4.7、3.4.12中的δ

步骤3.4.3.1，记δ

步骤3.4.3.2，记由集合Z构成的无向图G中节点A的邻居节点为节点q′。遍历所有节点q′，若

步骤3.4.3.3，遍历完所有节点q′所得δ

步骤3.4.11中计算

步骤3.4.11.1，记

步骤3.4.11.2，记由集合Z构成的无向图G中节点v

步骤3.4.11.3，当前

步骤3.6中对当前格局集合X执行最佳的变换操作

步骤3.6.1，将节点u

步骤3.6.2，根据当前集合Z，重新计算集合

步骤3.6.3，更新变换禁止标记数组tt中u

图3为从给定无向图，使用本方法求取最小连通支配集的步骤示例图，其中黑色节点为集合Z中的节点，灰色节点为集合

表1为本方法计算结果与对比算法计算结果的比对表。其中每个方法对同一算例(算例名称与对比算法的引用文献中算例名称一致，且相同算例名称的算例相同)计算十次，记录连通支配集的节点个数的最小值、平均值以及获得连通支配集的平均时间。若方法对某算例不能每次计算均获得同等最优值，则不记录其平均时间。对比算法为RSN-TS(引用文献：X.～Wu,Z.～Lü,P.～Galinier,Restricted swap-based neighborhood search fortheminimum connected dominating set problem,Networks 69～(2)(2017)222--236.)与ACO-RVNS(引用文献：S.～Bouamama,C.～Blum,J.-G.Fages,An algorithm based onant colonyoptimization for the minimum connected dominating set problem,Applied SoftComputing 80(2019)672--686.)。

表1本方法计算结果与对比算法计算结果的比对表

本文中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并不会偏离本发明的精神或者超越所附权利要求书所定义的范围。