本发明提供了一种的移动无线自组网覆盖连通方法，首先建立移动无线自主网的覆盖连通模型，设计出一种新的网络连通性方法；然后提出一种改进的自适应离子运动算法，并设计出基于同异性协同最优引导的液态离子更新方法和基于排名分类进化的固态离子更新方法；最后利用提出的离子运动算法优化覆盖连通模型。该方法能够同时最优化网络覆盖率和连通性，有效提升移动无线自主网的整体性能。
1.一种移动无线自组网覆盖连通方法，其特征在于，包括如下步骤：步骤1：建立移动无线自组网节点感知模型；
步骤1包括：所述移动无线自组网节点感知模型包括移动节点和中继节点，设定移动节点的通信半径为r，中继节点的通信半径为R；移动节点和中继节点的感知区域就是以各自位置为中心、通信半径为半径的圆形区域；
步骤2.2：建立移动无线自组网覆盖率函数连通性函数；
步骤2.3：建立移动无线自组网覆盖连通模型F(X)；
步骤2.1包括：将监测区域离散网格化；计算所有处于工作状态的节点感知的网格总数其中，i＝1,2,…,N，N为工作节点数量， 为每个移动节点感知的网格数，计算出整个监测区域的网格总数Gtotal，建立移动无线自组网覆盖率函数CR为：步骤2.2包括：计算所有工作节点之间的距离，记为距离矩阵D；判断距离矩阵D中每个元素与节点通信半径r的大小关系，以此建立处于工作状态节点间的连通状态，即连通矩阵L，记dij为节点i与节点j之间的距离，lij如式(2)所示：参数lij用于判断节点i和节点j是否连通，如果是则lij为1，否则lij为0；
移动无线自组网的所有节点具有连通性必须满足如下两个条件：条件1：Rank(L)＝N；
条件1表示连通矩阵L的秩为N，保证任意节点都有与之通信的节点存在；条件2表示连通矩阵所有元素的和大于等于2(N‑1)，保证任意节点至少存在另外一个节点能够与之通信；
为此，建立移动无线自组网覆盖率函数连通性函数C为：max C＝max Rank(L) (3)式中，Rank为求秩函数；
步骤2.3包括：建立移动无线自组网覆盖连通模型F(X)为：F(X)＝max[CR(X),C(X)] (5)式中，X＝[x1,x2,…,xN]为N维变量，xi＝[lxi,lyi]为第i个移动节点的二维平面位置坐标，lxi,lyi分别表示第i个移动节点的二维平面横坐标和纵坐标；
步骤3.1：设置初始参数，包括离子种群的规模P最大进化迭代次数Gmax；
步骤3.2：随机生成初始化离子种群X1,…,Xi,…,XP，Xi＝[x1,…,xj,…,xN]，xj＝[lxj,lyj]为第j个节点的位置，XP表示离子种群中的第P个离子；将离子种群一分为二，即为阴离子种群和阳离子种群；计算每个离子的目标函数值F(Xi)＝[CR(Xi),C(Xi)]，将目标函数值转为适应度值：
E＝w1×CR+w2×C (6)其中，E为离子的适应度值，w1和w2为权重参数；
步骤3.3：进行基于同异性协同最优引导策略的离子种群液态状态更新，并计算新种群阴阳离子的目标函数值：
Ai(t+1)＝Ai(t)+z×AFi×(Cbest(t)‑Ai(t))+(1‑z)×AFi×(Abest(t)‑Ai(t))t t
Ci(t+1)＝Ci(t)+z×CFi×(Abest(t)‑Ci(t))+(1‑z)×CFi×(Cbest(t)‑Ci(t)) (7)t
其中，t为进化迭代次数，Ai(t)代表第i个阴离子的位置，AFi 代表第i个阴离子的吸引t
力系数，Ci(t)代表第i个阳离子的位置，CFi 代表第i个阳离子的吸引力系数，z是0和1之间的随机数；Abest(t)为第t次迭代时阴离子种群中适应度最优的阴离子，Cbest(t)表示第t次迭代时阳离子种群中适应度最优的阳离子；
步骤3.4：进行基于排名分类进化策略的离子种群固态状态更新；
步骤3.4包括：分别将新的阴阳离子按照目标函数值排序，即阴离子种群一分为二，阳离子种群一分为二：
其中，FitCi(t)表示阳离子Ci的适应度，FitAi(t)为阴离子Ai的适应度，NUM为阴阳离子种群的离子数量，EAi(t)第i个阴离子的适应度值，ECi(t)为第i个阳离子的适应度值；
适应度值靠前的阴、阳离子的更新方式为：其中，rand([a,b])为在a和b之间的随机数；
适应度值靠后的阴、阳离子的更新方式为：Ai(t+1)＝Ai(t)+rand()×(Abest(t)‑Ai(t))+rand()×(Abest‑Ai(t)) (12)Ci(t+1)＝Ci(t)+rand()×(Cbest(t)‑Ci(t))+rand()×(Cbest‑Ci(t)) (13)步骤3.5：判断终止条件：如果t＝Gmax，则将离子种群中适应度值最优的解作为结果输出，否则，t＝t+1，返回步骤3.3。
一种移动无线自组网覆盖连通方法
技术领域
[0001] 本发明属于无线传感网络领域，尤其涉及一种移动无线自组网覆盖连通方法。
背景技术
[0002] 移动无线自组网是一种分布式、无中心、多跳的自主网络，被广泛应用于环境监测、救援救灾、军事通信等领域。由于移动无线自组网具有多跳传输、动态拓扑、节点资源受
限等特点，其网络结构的可靠性相对薄弱并容易受到各种干扰，在这种趋势移动无线自组
网的资源管理技术显得尤为重要。针对这一复杂的多目标优化问题，将目前计算智能领域
的优秀算法用于移动无线自组网的资源管理问题研究中，具有十分重要的现实意义。
发明内容
[0003] 发明目的：为解决背景技术中存在的技术问题，本发明提出一种移动无线自组网覆盖连通方法，针对现有算法往往只能优化单一目标而难以用于实际的问题，通过建立一
种新的连通性保障机制，并设计包括覆盖率和连通性的移动无线自组网覆盖连通模型；针
对离子运动算法易陷入局部最优、收敛精度不高的问题，提出基于同异性协同最优引导的
液态离子更新策略和基于排名分类进化的固态离子更新策略，设计出新的自适应离子运动
算法；将提出的新算法用于移动无线自组网覆盖率和连通性的同时最优化，进而提升网络
覆盖性能。
[0004] 本发明具体提供了一种移动无线自组网覆盖连通方法，包括如下步骤：
[0005] 步骤1：建立移动无线自组网节点感知模型；
[0006] 步骤2：建立移动无线自组网覆盖连通模型；
[0007] 步骤3：最优化移动无线自组网的覆盖率和连通性。
[0008] 步骤1包括：所述移动无线自组网节点感知模型包括移动节点和中继节点，设定移动节点的通信半径为r，中继节点的通信半径为R；移动节点和中继节点的感知区域就是以
各自位置为中心、通信半径为半径的圆形区域。
[0009] 步骤2包括：
[0010] 步骤2.1：建立移动无线自组网覆盖率函数；
[0011] 步骤2.2：建立移动无线自组网覆盖率函数连通性函数；
[0012] 步骤2.3：建立移动无线自组网覆盖连通模型F(X)。
[0013] 步骤2.1包括：将监测区域离散网格化；计算所有处于工作状态的节点感知的网格总数 其中，i＝1,2,…,N，N为工作节点数量， 为每个移动节点感知的网
格数，计算出整个监测区域的网格总数Gtotal，建立移动无线自组网覆盖率函数CR为：
[0014]
[0015] 步骤2.2包括：计算所有工作节点之间的距离，记为距离矩阵D；判断距离矩阵D中每个元素与节点通信半径r的大小关系，以此建立处于工作状态节点间的连通状态，即连通
矩阵L，记dij为节点i与节点j之间的距离，lij如式(2)所示：
[0016]
[0017]
[0018] 参数lij用于判断节点i和节点j是否连通，如果是则lij为1，否则lij为0；
[0019] 移动无线自组网的所有节点具有连通性必须满足如下两个条件：
[0020] 条件1：Rank(L)＝N；
[0021] 条件2：Sum(L)≥2(N‑1)；
[0022] Sum(L)表示连通矩阵L中的所有元素的和；
[0023] 条件1表示连通矩阵L的秩为N，保证任意节点都有与之通信的节点存在；条件2表示连通矩阵所有元素的和大于等于2(N‑1)，保证任意节点至少存在另外一个节点能够与之
通信；
[0024] 为此，建立移动无线自组网覆盖率函数连通性函数C为：
[0025] max C＝max Rank(L) (3)
[0026]
[0027] 式中，Rank为求秩函数。
[0028] 步骤2.3包括：建立移动无线自组网覆盖连通模型F(X)为：
[0029] F(X)＝max[CR(X),C(X)] (5)
[0030] 式中，X＝[x1,x2,…,xN]为N维变量，xi＝[lxi,lyi]为第i个移动节点的二维平面位置坐标，lxi,lyi分别表示第i个移动节点的二维平面横坐标和纵坐标。
[0031] 步骤3包括：
[0032] 步骤3.1：设置初始参数，包括离子种群的规模P最大进化迭代次数Gmax；
[0033] 步骤3.2：随机生成初始化离子种群X1,…,Xi,…,XP，Xi＝[x1,…,xj,…,xN]，xj＝[lxj,lyj]为第j个节点的位置，XP表示离子种群中的第P个离子；将离子种群一分为二，即为
阴离子种群和阳离子种群；计算每个离子的目标函数值F(Xi)＝[CR(Xi),C(Xi)]，将目标函
数值转为适应度值：
[0034] E＝w1×CR+w2×C (6)
[0035] 其中，E为离子的适应度值，w1和w2为权重参数；
[0036] 步骤3.3：进行基于同异性协同最优引导策略的离子种群液态状态更新，并计算新种群阴阳离子的目标函数值：
[0037] Ai(t+1)＝Ai(t)+z×AFit×(Cbest(t)‑Ai(t))+(1‑z)×AFit×(Abest(t)‑Ai(t))
[0038] Ci(t+1)＝Ci(t)+z×CFit×(Abest(t)‑Ci(t))+(1‑z)×CFit×(Cbest(t)‑Ci(t)) (7)
[0039] 其中，t为进化迭代次数，Ai(t)代表第i个阴离子的位置，AFit代表第i个阴离子的t
吸引力系数，Ci(t)代表第i个阳离子的位置，CFi代表第i个阳离子的吸引力系数，z是0和1
之间的随机数；Abest(t)为第t次迭代时阴离子种群中适应度最优的阴离子，Cbest(t)表示
第t次迭代时阳离子种群中适应度最优的阳离子；
[0040] 步骤3.4：进行基于排名分类进化策略的离子种群固态状态更新。
[0041] 步骤3就是利用离子运动算法来优化等式(6)，即同时优化覆盖率和连通性目标，使得它们同时最优。
[0042] 步骤3.4包括：分别将新的阴阳离子按照目标函数值排序，即阴离子种群一分为二，阳离子种群一分为二：
[0043]
[0044]
[0045] 其中，FitCi(t)表示阳离子Ci的适应度，FitAi(t)为阴离子Ai的适应度，NUM为阴阳离子种群的离子数量，EAi(t)第i个阴离子的适应度值，ECi(t)为第i个阳离子的适应度值；
[0046] 适应度值靠前的阴、阳离子的更新方式为：
[0047]
[0048]
[0049] 其中，rand([a,b])为在a和b之间的随机数；
[0050] 适应度值靠后的阴、阳离子的更新方式为：
[0051] Ai(t+1)＝Ai(t)+rand()×(Abest(t)‑Ai(t))+rand()×(Abest‑Ai(t)) (12)
[0052] Ci(t+1)＝Ci(t)+rand()×(Cbest(t)‑Ci(t))+rand()×(Cbest‑Ci(t)) (13)
[0053] 步骤3.5：判断终止条件：如果t＝Gmax，则将离子种群中适应度值最优的解作为结果输出，否则，t＝t+1，返回步骤3.3。
[0054] 有益效果：本发明设计出一种新的无线自组网覆盖连通性机制，提出一种自适应离子运动算法，并将覆盖率和连通性合并为适应度函数，最后利用提出的算法来优化覆盖
连通模型。不仅能够同时最优化无线自组网的覆盖率和连通性，从而提高其整体性能和服
务质量；而且提出的改进算法提高了收敛速度，保障算法能够快速提供一种覆盖连通方案，
实时调整无线自组网的运行情况，从而保障其实际应用。
附图说明
[0055] 下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/或其他方面的优点将会变得更加清楚。
[0056] 图1为移动无线自组网节点感知模型示意图。
[0057] 图2为本发明方法流程图。
具体实施方式
[0058] 本发明提供了一种移动无线自组网覆盖连通方法，包括如下步骤：
[0059] 步骤1：建立移动无线自组网节点感知模型。移动无线自组网中主要包括移动节点和中继节点，设定移动节点的通信半径为r，中继节点的通信半径为R，则移动无线自组网节
点感知模型如图1所示。
[0060] 步骤2：建立包括覆盖率和连通性的移动无线自组网覆盖连通模型，设计出新的连通保障机制。
[0061] 步骤2.1：建立移动无线自组网覆盖率函数。将监测区域离散网格化；计算所有工作节点感知的网格总数 其中，i＝1,2,…,N，N为工作节点数量， 为每个
移动节点感知的网格数；计算出整个监测区域的网格总数Gtotal；建立移动无线自组网的覆
盖率函数CR为：
[0062]
[0063] 步骤2.2：建立移动无线自组网覆盖率函数连通性函数。计算所有工作节点之间的距离，记为距离矩阵D；判断距离矩阵D中每个元素与节点通信半径r的大小关系，以此建立
处于工作状态节点间的连通状态，即连通矩阵L。其中，N为工作的节点数量，dij为节点i与节
点j之间的距离，lij如式(2)所示。
[0064]
[0065]
[0066] 由于连通矩阵L为对称矩阵，且其中的元素非0即1。为此，移动无线自组网的所有节点具有连通性必须满足如下两个条件：1)Rank(L)＝N；2)Sum(L)≥2(N‑1)。条件1表示连
通矩阵L的秩为N，保证任意节点都有与之通信的节点存在。条件2表示连通矩阵所有元素的
和大于等于2(N‑1)，保证任意节点至少存在另外一个节点可以与之通信。
[0067] 为此，建立移动无线自组网的连通性函数C为：
[0068] max C＝max Rank(L) (3)
[0069]
[0070] 式中，L为节点间的连通矩阵，Rank为求秩函数，N为移动无线自组网的工作节点数量。
[0071] 步骤2.3：建立移动无线自组网覆盖连通模型F(X)为：
[0072] F(X)＝max[CR(X),C(X)] (5)
[0073] 式中，X＝[x1,x2,…,xN]为N维变量，N为移动无线自组网的工作节点数量，xi＝[lxi,lyi]为第i个移动节点的二维平面位置坐标，i＝1,2,…,N。
[0074] (步骤3根据步骤2，提出用于覆盖率和连通性同时最优化的自适应离子运动算法)
[0075] 步骤3：提出基于同异性协同最优引导策略和基于排名分类进化策略的自适应离子运动算法，同时最优化移动无线自组网的覆盖率和连通性。
[0076] 步骤3.1：设置初始参数，包括离子种群的规模N，最大进化迭代次数Gmax。
[0077] 步骤3.2：随机生成初始化离子种群X1,…,Xi,…,XN，Xi＝[x1,…,xj,…,xN]，xj＝[lxj,lyj]为节点位置；将离子种群一分为二，即为阴离子种群和阳离子种群；计算每个离子
的目标函数值F(Xi)＝[CR(Xi),C(Xi)]，将目标函数值转为适应度值。
[0078] E＝w1×CR+w2×C (6)
[0079] 其中，E为离子的适应度值，w1＝w2＝0.5，
[0080] 步骤3.3：进行基于同异性协同最优引导策略的离子种群液态状态更新，并计算新种群阴阳离子的目标函数值。
[0081] Ai(t+1)＝Ai(t)+z×AFit×(Cbest(t)‑Ai(t))+(1‑z)×AFit×(Abest(t)‑Ai(t))
[0082] Ci(t+1)＝Ci(t)+z×CFit×(Abest(t)‑Ci(t))+(1‑z)×CFit×(Cbest(t)‑Ci(t)) (7)
[0083] 其中，t为进化迭代次数，Ai(t)代表第i个阴离子的位置，AFit代表第i个阴离子的t
吸引力系数，Ci(t)代表第i个阳离子的位置,CFi代表第i个阳离子的吸引力系数，z是0和1
之间的随机数。
[0084] 步骤3.4：进行基于排名分类进化策略的离子种群固态状态更新。
[0085] 分别将新的阴阳离子按照目标函数值排序，即阴离子种群一分为二，阳离子种群一分为二。
[0086]
[0087]
[0088] 其中，NUM为阴阳离子种群的离子数量，EAi(t)第i个阴离子的适应度值，ECi(t)为第i个阳离子的适应度值。
[0089] 适应度值靠前的阴、阳离子的更新方式为：
[0090]
[0091]
[0092] 其中，t为进化迭代次数，rand([a,b])为在a和b之间的随机数。
[0093] 适应度值靠后的阴、阳离子的更新方式为：
[0094] Ai(t+1)＝Ai(t)+rand()×(Abest(t)‑Ai(t))+rand()×(Abest‑Ai(t)) (12)
[0095] Ci(t+1)＝Ci(t)+rand()×(Cbest(t)‑Ci(t))+rand()×(Cbest‑Ci(t)) (13)
[0096] 步骤3.5：判断终止条件。若t＝Gmax，则算法停止并将离子种群中适应度值最优的解作为结果输出，否则，t＝t+1，返回步骤3.3。
[0097] 本发明提供了一种移动无线自组网覆盖连通方法，具体实现该技术方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人
员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应
视为本发明的保护范围。本实施例中未明确的各组成部分均可用现有技术加以实现。
