ISSN 
-
近年来，无线视频传感器(其感知具有方向性，隶属于有向传感器)逐渐取代有线视频监控传感器，其安装简便，价格便宜，应用场景不断拓展。传感器网络节点覆盖调度对于网络同步与分布式优化起着重要作用[1-4]。在满足监测目标监测覆盖的要求下，如何借助节点调度算法延长有向传感器网络的工作时间是有向传感器网络的重要研究内容。文献[5]提出一种基于概率覆盖圆的连通有向传感器网络的目标覆盖增强算法。文献[6]提出了一种面向有向传感器网络的基于遗传算法的k覆盖算法，通过求解多个满足目标k覆盖要求且节点数量最少的集合延长网络的寿命。文献[7]通过建立一种混合二进制整数线性规划模型，求解得到多个互不相交的覆盖集合来延长有向传感器网络的寿命。这些研究都是假设参与节点调度的传感器节点参数相同，未考虑异构节点对调度算法的影响。同时，均假定监测目标在区域内均匀分布，未考虑监测目标的重要性、出现频率对网络服务质量的影响。对于异构有向传感器网络，文献[8]提出两种启发式算法解决有向传感器网络的寿命最大化问题，两种算法的区别在于每次选取节点感知方向的标准不同。一种为每次选取对目标覆盖贡献最大(也就是覆盖最多目标)的感知方向，另一种为每次选择能覆盖监测目标且能量最少的感知方向，两种算法结束的条件均为直到所有的目标满足覆盖要求。文献[9]提出一种基于学习自动机的算法解决感知半径可调的有向传感器网络的k-覆盖问题。文献[10]提出一种基于遗传算法的寿命最大化策略来延长半径可调的有向传感器网络的寿命。针对异构有向传感器网络的寿命优化问题，利用集合覆盖的思想，文献[11]通过改进的和声搜索算法求解满足目标覆盖要求的集合，解决差异化覆盖条件下异构有向传感网络寿命的问题。文献[12]将学习自动机引入差分进化算法，实现算法参数的自适应并增强算法的优化能力，使寿命达到最大化。但这些文献没有考虑网络的连通性，使得算法在工程实践中受到影响。尽管文献[13-14]对差异化覆盖连通问题进行了研究，但其研究对象为全向感知和节点同构的传感器网络，研究成果不适用于感知模型为有向的异构有向传感器网络。
针对上述研究中存在的问题，在满足应用场景监测目标覆盖要求差异化和网络连通的条件下，本文提出一种面向异构有向传感器网络的节点调度算法，达到降低网络能耗和延长网络工作时长的目标。
-
在二维监测区域中随机部署N个不同的感知半径ri、通信半径ci、携带能量Ei、感知角度
$ {\theta }_{i} $ 的传感器节点si (i =1, 2, ···, N)，用于监测W个目标。由节点的感知角度得出可用的感知方向为$\dfrac{2{\text{π}} }{{\theta }_{i}}$ ，本文假定节点的感知方向不重叠，在工作状态时传感器节点消耗的能量ei不同，非工作状态时节点不消耗能量，则可得出节点的寿命为$ {L}_{i}={E}_{i}/{e}_{i} $ 。根据监测目标出现的频率将其分为重点目标(出现频率高)和非重点目标。为保证网络服务质量和网络可靠性，要求至少两个传感器节点对对重点目标进行监测，其他目标只要能监测到就符合应用需求。定义 传感网络的寿命[12]网络中的传感器节点能提供符合监测目标的监测要求且能保持网络连通的时间。
在满足监测目标的监测覆盖需求和保持网络连通的前提下，如何延长传感网络的寿命是本文要解决的问题。其形式化的描述为：
$$ \text{Max}\;{t}_{1}+{t}_{2}+\cdots +{t}_{k} $$ (1) $$ \text{s}\text{.t}\text{.}{\displaystyle \sum _{k=1}^{K}{\displaystyle \sum _{j=1}^{\left|{D}_{i}\right|}{b}_{i,j,k}{e}_{i}\leqslant {E}_{i}\begin{array}{cc}& \end{array}}}i\in [1,K] $$ (2) $$ {\displaystyle \sum _{j=1}^{\left|{D}_{i}\right|}{b}_{i,j,k}\leqslant 1\begin{array}{cc}& \end{array}}i,k\in [1,N] $$ (3) $$ \begin{split} &\qquad\qquad{\displaystyle \sum _{{D}_{i,j}\in C\_{T}_{k,m}}{b}_{i,j,k}\geqslant \mathrm{Req}({T}_{m})}\\ & k\in [1,K],m\in [1,W],\;{b}_{i,j,k}=\left\{ {\begin{array}{*{20}{l}} {1}&{{D}_{i,j}\in {C}_{k}}\\ {0}&{其他} \end{array}} \right. \end{split} $$ (4) $$ {\displaystyle \sum _{j=1}^{N}{\text{con}}_{i,j}\geqslant 1}\;\;\;\;j\ne i且1\leqslant i,j\leqslant N $$ (5) $$ {\text{con}}_{i,j}=\left\{ {\begin{array}{*{20}{l}} {1}&{节点{s}_{i}与节点{s}_{j}连通}\\ {0}&{其他} \end{array}} \right.$$ 除了增加式(5)的连通要求，该数学模型与文献[11]相同。式中，
$K$ 表示满足覆盖连通要求的集合数；${t_k}$ 为第$k$ 个覆盖连通集的工作时长，其大小由集合中能量最小的节点决定；${D_{i,j}}$ 为节点${s_i}$ 的第$j$ 个感知方向；${C_k}$ 为第$k$ 个符合连通覆盖要求的节点集合；$C\_{T_{k,m}}$ 表示在${C_k}$ 中能覆盖监测目标${T_m}$ 的感知方向的集合；${{\rm{Re}}} {\text{q}}({T_m})$ 表示监测目标${T_m}$ 要求同时被多少个传感器节点监测，取值为正整数，由目标本身的特性或出现的区域决定。采用文献[15]中的有边界的帕累托分布模拟目标在某一时间段内的出现情况，其参数取值与文献[15]相同，仿真结果如图1所示。其中，“□”目标出现频繁的区域为重点区域，对于这些区域的监测目标要求${{\rm{Re}}} {\text{q}}({T_m}) \geqslant 2$ ，其他区域${{\rm{Re}}} {\text{q}}({T_m}) = 1$ 即可。式(2)对节点的能量进行约束，使得其工作时消耗的总能量不超过其携带的总能量。式(3)表示传感器节点在工作状态时只能有一个感知方向。式(4)表示由传感器节点构成的集合能满足所有监测目标要求。式(5)保证传感器节点之间是相互连通的，本文假定传感器节点在其通信半径内有其他节点存在时则该节点连通的。
图 1 监测目标出现区域示意图
考虑到集合覆盖问题为NP-hard问题[11]，本文利用珊瑚礁算法进行求解。
-
珊瑚礁算法[16]是一种模拟珊瑚虫行为的智能进化算法，已用于求解农场风力资源优化、有向传感器网络资源优化[17]等组合优化问题。该算法的步骤为：初始化、繁殖过程、竞争过程和淘汰过程。其中，种群初始化实现算法参数的初始化，包括：珊瑚礁的面积(通常为W×L矩形)、珊瑚礁中存在珊瑚虫的比例pro、迭代数I_MAX、非性繁殖(即雌雄同体)的比重Fa
、迭代过程中子代寻找珊瑚礁附着时允许尝试的最大次数T_MAX、珊瑚虫被淘汰的概率pro_coral和被淘汰珊瑚虫与珊瑚虫总数的比重pro_no。珊瑚虫的繁殖行为包括：非性繁殖行为(其比例占所有繁殖行为的比例为Fa)和在符合要求范围内随机产生子代和有性繁殖行为(其比例占所有繁殖行为的比例为Fb)。珊瑚虫竞争珊瑚礁的过程，也就是珊瑚虫寻找可附着珊瑚礁的过程。若该珊瑚礁上没有其他珊瑚虫，则珊瑚虫直接可占据此珊瑚礁；否则，需要进行珊瑚虫适应度大小的比较，根据比较结果择优附着在珊瑚礁上。若竞争失败，可尝试占据其他珊瑚礁，若达到最大尝试次数仍未找到可附着的珊瑚礁，则该珊瑚虫死亡。在淘汰过程中，依据适应度排序，对珊瑚虫进行淘汰操作。淘汰后的珊瑚虫其附着的珊瑚礁随之被空出，以备后续珊瑚虫使用。 -
1) 种群初始化策略的改进
种群初始化后产生的初始解对算法的优化能力具有非常重要的影响。为了使初始解均匀分布，将种群数均匀分为两部分，每一部分采用不同的初始化策略。第一部分种群使用低差异的SOBOL序列产生，使得初始解更均匀的分布在多维超体中[18]。其数学表达式为：
$$ {P_n} = L + S(H - L) $$ (6) 式中，变量L和H分别表示解允许取值范围的最小值和最大值；S为SOBOL序列产生的[0,1]的随机数。
第二部分种群使用反向学习产生，先随机产生种群中每个染色体的初始值
$P = ({p_1},{p_2}, \cdots ,{p_n})$ ,${p_i} \in [L,H]$ ，每个染色体的基因为：$$ p_i' = L + (H - {p_i}) $$ (7) 2)非性繁殖过程的改进
CRO算法中的非性繁殖过程是随机产生的，这种操作不利于继承种群中的较优解。为保存非性繁殖过程中的优秀解，借鉴生物地理学算法[19]、和声搜索算法[20]和差分进化算法[12]对其进行改进。具体为，子代个体中每一维的来源有3种可能：① 直接来自父代的概率为
$1-{\lambda _i}$ ，为避免继承较差的基因，以概率PAR[20]对其进行随机扰动；② 在可行区域内随机产生，其概率为${\lambda _i}(1 - {c_r} - 1 / D)$ ，cr为差分进化算法中的交叉概率，本文取0.9[12]。③ 剩余的${\lambda _i}({c_r} + {1 \mathord{\left/ {\vphantom {1 D}} \right. } D})$ 的概率来自非性繁殖父代个体之间的差分变异操作。变量${\lambda _i}$ 为生物地理学算法的参数，为解的第i维迁移率[19]，${\lambda _i} = {i \mathord{\left/ {\vphantom {i D}} \right. } D}$ ，参数D是解的维数；PAR为来自和声搜索算法的参数，采用文献[20]自适应缩放因子，即：$$ {\text{PA}}{{\text{R}}_k} = {\text{PA}}{{\text{R}}_{\min }} + ({\text{PA}}{{\text{R}}_{\max }} - {\text{PA}}{{\text{R}}_{\min }}){k \mathord{\left/ {\vphantom {k K}} \right. } K} $$ 式中，k为当前的迭代次数；K为最大迭代次数；
${\text{PA}}{{\text{R}}_{\max }} = 0.8$ ；${\text{PA}}{{\text{R}}_{\min }} = 0.8$ [20]。差分变异操作中差分变异策略和控制参数对算法的性能有重要影响。为增强算法性能，采用自适应变异策略和设置控制参数，变异策略为：
$$ {V}_{i}^{t} = \left\{ \begin{array}{l} {X}_{r1}^{t} + F({X}_{r2}^{t}-{X}_{r3}^{t})\;\;\;\; f({X}_{i}^{t}) > {f}_{\text{avg}}({X}^{t})\\ {X}_{r1}^{t} + F({X}_{r2}^{t}-{X}_{r3}^{t}) + F({X}_{{\rm{best}}}^{t}-{X}_{r1}^{t})\;\;\;\; f({X}_{i}^{t}) > f({X}_{r1}^{t})或\\ f({X}_{i}^{t}) > f({X}_{r2}^{t})或f({X}_{i}^{t}) > f({X}_{r3}^{t})\\ {X}_{{\rm{best}}}^{t} + F({X}_{r2}^{t}-{X}_{r3}^{t}) + F({X}_{r4}^{t}-{X}_{r5}^{t})\;\;\;\; 其他情况 \end{array} \right.$$ 式中，r1，r2，r3，r4，r5为种群中不同于i的个体；
$X_{{\text{best}}}^t$ 为迭代次数为t时种群中适应度最好的个体；$f(X_i^t)$ 表示个体$X_i^t$ 的适应度；${f_{{\text{avg}}}}({X^t})$ 表示迭代次数为t时种群的平均适应度。采用自适应的参数选择策略，具体为：
$$ F = \left\{ \begin{array}{l} {F}_{\mathrm{max}}\;\;\;\;f({X}_{i}^{t}) > {f}_{{\rm{avg}}}({X}^{t})\\ {F}_{\mathrm{min}} + \text{rand}()\times ({F}_{\mathrm{max}}-{F}_{\mathrm{min}})\;\;\;\; ({X}_{i}^{t}) > f({X}_{r1}^{t})或f({X}_{i}^{t}) >\\ f({X}_{r2}^{t})或f({X}_{i}^{t}) > f({X}_{r3}^{t})\\ {F}_{\mathrm{min}}\;\;\;\;其他情况 \end{array} \right.$$ 式中，
${F_{\min }}$ 和${F_{\max }}$ 分别表示F的最小值和最大值。当种群个体有早熟的趋势时，采用较大的F值进行抑制，保持种群的多样性；反之，当种群个体收敛较慢时，采用较小的F值加快种群的收敛；其他情况下，产生随机的F。3)混合策略提升种群中的最差个体
在竞争和淘汰过程之间增加最差个体提升过程，通过两种方法改善其优化能力，并通过适应度评价选择两种方法中改善效果最显著的作为其最终的结果。如式(8)的反向学习操作和式(9)的差分操作：
$$ \begin{gathered} {V_{{\text{worst}}}} = L + {\text{rand}}() \times ({{(H - L)} \mathord{\left/ {\vphantom {{(H - L)} 2}} \right. } 2} - V_{{\text{worst}}}^t) + \hfill \\ (1 - {\text{rand}}())(V_{{{\rm{worst}}} }^t - {{(H - L)} \mathord{\left/ {\vphantom {{(H - L)} 2}} \right. } 2})\quad \quad \end{gathered} $$ (8) $$ {V_{{\text{worst}}}} = V_{{\text{worst}}}^t + F(V_{{\text{best}}}^t - V_{{\text{worst}}}^t)\;\quad \;\quad $$ (9) 式中，变量L和H分别表示解的最小值和最大值；函数rand()为产生0~1的随机数；
$V_{{\text{worst}}}^t$ 和$V_{{\text{best}}}^t$ 分别为循环次数为t时种群中适应度最差和最好的个体；F为差分参数，在区间[0.1, 0.9]随机取值。通过适应度评价，选择式(8)和式(9)中表现较好的作为最差个体新的解，可使其跳出其目前所处最差区域，增强其优化能力。 -
通过求解尽可能多满足覆盖连通要求的集合，达到延长网络寿命的目的。每次循环完毕后，珊瑚礁算法输出种群中的最优解，执行节点能量的更新，反复迭代，直到满足算法终止的条件。其中要解决解质量的评价和如何表示解这两个关键问题。
1) 解质量的评价
对于珊瑚礁算法而言，解质量的评价也就是设计健康度函数。针对解决问题的特点，设计了3个优化目标：① 形成尽可能多的满足监测要求的集合；② 形成满足要求的集合后，节点的剩余能量最多；③ 最后一个是要求集合中节点的连通度越高越好。用形式化的语言描述为：
$$ {f_1} = \frac{{W'}}{W}\;\;\; {f_2} = \tanh (\beta \sum\limits_{i = 1}^N {{E_i}} )\;\;\; {f_3} = \frac{1}{N}\sum\limits_{i = 1}^N {y({s_i})} $$ $$ y({s}_{i})=\left\{ {\begin{array}{*{20}{l}} {1}& {{\text{con}}_{i,j}\geqslant 1}\\ {0}&{其他} \end{array}} \right.$$ (10) 式中，
$W'$ 表示符合监测覆盖要求的监测目标数量；W表示监测目标的数量；${f_1}$ 的值域为[0,1]；${f_2}$ 是用双曲正切函数表示的剩余能量的函数，取值范围为[0,1]；β是权重系数，在文中设为1；${f_3}$ 值域为[0,1]。利用随机线性加权的方法[21]将多目标优化问题变成单目标优化问题，即：
$$ \begin{gathered} {\text{Fit}}(X) = {\gamma _1}{f_1} + {\gamma _2}{f_2} + {\gamma _3}{f_3} \hfill \\ {\gamma _i} = {{{\text{ran}}{{\text{d}}_i}} \mathord{\left/ {\vphantom {{{\text{ran}}{{\text{d}}_i}} {\sum\limits_{i = 1}^3 {{\text{ran}}{{\text{d}}_i}} }}} \right. } {\sum\limits_{i = 1}^3 {{\text{ran}}{{\text{d}}_i}} }} \hfill \\ \end{gathered} $$ 式中，
${\gamma _1}$ 、${\gamma _2}$ 和${\gamma _3}$ 为${f_1}$ 、${f_2}$ 和${f_3}$ 对应的系数；${\text{ran}}{{\text{d}}_i}$ 为区间(0,1)之间的随机数。2) 解的表示
考虑到求解问题的特点，对节点和感知方向进行整数编号，根据该编号能确定属于节点的感知方向，如图2所示。
图 2 解的示意图
$$ \begin{split} {t}_{i}=\left\{ {\begin{array}{*{20}{l}} {0}& {\;\;没有节点的感知方向用来监测{t}_{i}}\\ {}&{\;\;编号为j的感知方向处于工作状态，}\\ {j}& {j=1,2,\cdots ,{\displaystyle \sum _{i=1}^{N}\left|{D}_{i}\right|}} \end{array}} \right.\\[-30pt] \end{split}$$ (11) 图中解的每个位置
${t_i}$ 的含义如式(11)所述，其中$\left| {{D_i}} \right|$ 为有向传感器节点${s_i}$ 感知方向的数量。由于节点冗余性和特定节点的某个感知方向可覆盖多个监测目标，可能出现解的某个位置的值为0的情况。 -
按照珊瑚礁算法步骤，对本文提出的ECRO算法进行时间复杂度的理论分析。种群初始化包括解的表示和健康度函数评价两个过程，其时间复杂度为
${\text{TC}}1 = O(WL \times {\text{pro}} \times D) + O{(WL \times {\text{pro}})^2}$ ，D为解的维数也就是染色体的长度，其他参数的含义与前面相同，采用时间复杂度为$O{(WL \times {\text{pro}})^2}$ 排序算法完成健康度函数评价；新个体产生过程中，非性繁殖过程中直接来自父代和随机产生个体的时间复杂度之和，为${\text{TC}}2 = O((WL \times {\text{pro}} \times {F_a}D)[(1 - {\lambda _i}) \times 1 + {\lambda _i} \times (1 - {c_r} - {1 \mathord{\left/ {\vphantom {1 D}} \right. } D}) \times 1])$ ，来自父代个体差分变异操作的非性繁殖新个体按照式(8)～式(10)需要得到种群的平均适应度和适应度最好的个体，因此其所需的时间复杂度为${\text{TC}}3 = O(WL \times {\text{pro}} \times {F_a} \times I\_{\text{MAX}} \times {{D}} )^2 \times {\lambda _i} ({c_r} -1/D) $ ，有性繁殖过程的时间复杂度为${\text{TC}}4 = O((WL \times {\text{pro}} \times (1 - {F_a}) \times I\_{\text{MAX}}) \times D)^2 {\lambda _i}({c_r} + 1/D))$ ，竞争珊瑚礁过程中，每次迭代需要进行比较操作的数学期望为$\displaystyle\sum\limits_{i = 1}^{T\_{\text{MAX}}} {i \times {1 \mathord{\left/ {\vphantom {1 {T\_{\text{MAX = }}{{(1 + T\_{\text{MAX}})} \mathord{\left/ {\vphantom {{(1 + T\_{\text{MAX}})} 2}} \right. } 2}}}} \right. } {T\_{\text{MAX = }}{{(1 + T\_{\text{MAX}})} \mathord{\left/ {\vphantom {{(1 + T\_{\text{MAX}})} 2}} \right. } 2}}}}$ 。因此，时间复杂度为${\text{TC}}5 = O(WL \times {\text{pro}} \times I\_{\text{MAX}} (1 + T\_{\text{MAX}}) / 2)$ ；最差个体提升过程中，需要找到现有种群中健康度最差的个体，其所需的时间复杂度为${\text{TC}}6 = O(WL \times {\text{pro}})$ 。结合上述分析，ECRO算法的总的时间复杂度是上述所有过程时间复杂度的总和，即TC= TC1+ TC2+ TC3+ TC4+ TC5+ TC6
-
本节首先测试增强珊瑚礁算法ECRO在数值计算上的性能，然后将其用于解决异构有向传感器网络寿命最大化的问题。
-
在表1的4个测试函数上测试各算法的性能。将遗传算法(genetic algorithm, GA)、模拟退火算法(simulating algorithm, SA)、原始差分进化算法(differential evolution, DE)、文献[11]中的改进和声搜索算法(enhanced harmony search, EHS)和文献[12]中的基于学习自动机的差分进化算法(learning automata differential evolution, LADE)作为对比算法参与数值运算。函数的具体信息详见表1所示。
CRO算法中W×L设为10×5，其他参数
${F_b}$ 、${F_a}$ 、pro、T_MAX、pro_coral和pro_no分别设为0.9,0.1,0.7,3,0.1和0.01[16]；ECRO算法中${F_{\min }} = 0.1$ ，${F_{\max }} = 0.9$ [22] ，维数n为30，其他参数的值与文献[12]取值相同。算法结果为程序运行30次所得结果的平均值。从表2的求解结果可以得出：在F3函数中，所有参与测试的算法均取得全局优化解0；除此之外的数值测试结果显示，相比较于其他算法，ECRO算法求解结果最优。数值计算结果表明，与其他算法比较，本文提出的ECRO算法性能最佳，证明了算法的有效性。表 1 测试函数具体信息
测试函数 函数表达式 定义域 F1 ${f_1}(x) = \displaystyle\sum\limits_{i = 1}^n {{x^2}(i)} $ $x(i) \in [ - 100,100]$
F2${f_2}(x) = {\displaystyle\sum\limits_{i = 1}^n {(\displaystyle\sum\limits_{j = 1}^i {x(j))}^2 } }$
$x(i) \in [ - 100,100]$
F3${f_3}(x) = \displaystyle\sum\limits_{i = 1}^n {(\left\lfloor {x(i) + 0.5} \right\rfloor } {)^2}$ $x(i) \in [ - 100,100]$ F4 ${f_4}(x) = \displaystyle\sum\limits_{i = 1}^n {\left| {x(i)} \right|} + \prod\limits_{i = 1}^n {\left| {x(i)} \right|} $ $x(i) \in [ - 100,100]$ 表 2 结果比较
测试函数 算法 最佳结果平均值 最佳结果方差 F1 GA
SA
DE
LADE
CRO
EHS
ECRO3.69×10−4
1.21×10−4
5.91×10−5
4.39×10−5
5.24×10−5
4.01×10−5
1.35×10−64.30×10−4
1.36×10−4
1.35×10−4
1.04×10−4
1.09×10−4
1.00×10−4
1.03×10−6F2 GA
SA
DE
LADE
CRO
EHS
ECRO1.09×10−3
1.56×10−5
1.12×10−4
2.26×10−5
2.38×10−5
1.96×10−5
1.13×10−68.90×10−4
2.20×10−5
1.04×10−4
1.59×10−5
1.61×10−5
1.46×10−5
1.09×10−6F3 GA
SA
DE
LADE
CRO
EHS
ECRO3.74×10−2
6.10×10−6
0
0
0
0
03.48×10−2
6.44×10−6
0
0
0
0
0F4 GA
SA
DE
LADE
CRO
EHS
ECRO2.86×10−2
6.27×10−3
3.90×10−3
5.77×10−4
5.84×10−4
4.96×10−4
3.69×10−62.08×10−2
4.76×10−3
3.15×10−3
6.97×10−4
7.08×10−4
6.37×10−4
6.91×10−6 -
覆盖调度算法的仿真平台为MATLAB 2013。监测区域大小为50 m×50 m，节点数量N为30，每个连通覆盖集合工作时间wt=1s，节点可选的感知方向为
$\left|{D}_{i}\right|=\dfrac{2{\text{π }}}{{\theta }_{i}}$ ，且感知方向之间无重叠区域，其中$ {\theta }_{i} $ 表示感知角度$ {\theta }_{i} $ 。节点信息如表3所示。监测目标随机分布在监测区域内，其数量W=6。若某一监测目标在某个监测周期里出现频率较高，则认定为重点监测目标，此类监测目标要求被两个传感器节点监测到，其余监测目标被1个传感器节点监测到即可，每种类型的监测目标数量随机产生。表 3 节点参数表
类型 感知
半径/m通信
半径/m感知
角度$ {\theta }_{i} $节点
能量/J每个工作周期
消耗能量/J节点
数量1 10 20 ${{\text π} \mathord{\left/ {\vphantom {{\text π} 3}} \right. } 3}$ 100 0.1 10 2 20 40 ${{2{\text π} } \mathord{\left/ {\vphantom {{2{\text π} } 3}} \right. } 3}$ 200 0.5 10 3 15 30 $ {{\text π} \mathord{\left/ {\vphantom {{\text π} 2}} \right. } 2} $ 150 0.3 10 为更好地衡量改进算法ECRO的性能，本文提出一种贪婪算法(以下简称Greedy)作为对照算法。其求解步骤为，每一轮选择的感知方向，为以下3个指标乘积的最大值：1)该感知方向所在节点的剩余能量；2)该感知方向监测目标数量；3)该感知方向与其他已选择节点的连通性(式(5)不等号左端的值)。选择感知方向的操作会一直进行，直到所有监测目标的监测要求被满足，这样就产生了一个符合监测目标要求且连通的感知方向集合。执行节点能量更新操作后，继续下一轮集合的选择，直到不满足覆盖连通要求或节点因能量耗尽而死亡。
-
1) 收敛性能比较
将种群的平均适应度作为种群收敛性能的指标，进行算法收敛性能的比较，图3为ECRO和CRO算法的平均适应度变化情况。观察图3可以得出，ECRO和CRO两种算法都随着迭代次数变大而趋于收敛，并且ECRO算法种群的平均适应度大于CRO算法，验证了改进算法ECRO的收敛性能较好。同时，两种算法在未进入迭代(迭代次数为0)时，ECRO算法的种群平均适应度优于CRO算法，证明了本文提出的种群初始化策略的有效性。
2) 监测要求与网络寿命的关系
假定监测目标数目W=8，用
$M'$ 代表重点监测目标的数量，其值分别设为3和5；$k'$ 代表重点监测目标对应的监测覆盖要求，其值分别设为2和3，用ECRO算法求解覆盖连通问题。从图4求解得到的结果可以看出：1)节点数越多，网络寿命越长。2)节点数和监测覆盖要求$k'$ 固定时，重点目标数$M'$ 越大，相应地网络寿命也就越短。3)节点数和重点目标数$M'$ 固定时，重点目标的监测覆盖要求$k'$ 越大，网络寿命就越短。
图 3 算法平均适应度比较
图 4 不同覆盖要求对节点寿命的影响
3) 均匀比例下节点数量对网络寿命的影响
设置不同的节点总数，等比例混合3种类型的传感器节点，研究节点数量对网络寿命的影响。监测目标数为8，其他参数值与前面相同。从图5的求解结果可以得出：1)随着部署节点数的增加，网络的寿命也随之延长。究其原因在于，传感器节点数量的增加使得可选的用于工作的感知方向增多，导致满足监测覆盖需求的集合数目随之增加；2)在部署节点数固定的情况下，提出的ECRO算法明显优于其他算法。如当节点数为60时，与贪婪算法Greedy、LADE、未改进的CRO算法和EHS算法[12]相比，改进算法寿命分别延长97%、27.4% 、33.9%和21.5%。究其原因在于，贪婪算法尽管每一步都是当前最优，但局部最优不保证最终得到全局最优解。改进算法得益于种群初始化、算法过程和最差个体的改进，使得算法优化能力得以增强。
图 5 算法比较
4) 非均匀比例下节点数量对网络寿命的影响
研究非均匀比例对网络寿命的影响。表4为具体构成比例，其中情况1表示，3种类型的传感器节点数量都相同，也就是所占的比例均为1/3，情况2表示3种传感器节点数量不同，3种类型节点的参数详见表3。监测目标数设为8，其他的算法参数与前面相同。从图6的结果可以得出：1)对于某一算法，在部署节点数固定的条件下，与情况1相比，情况2中的网络寿命较好。如对于ECRO算法来说，当节点总数为90时，情形1的网络寿命为100 s，情形2网络寿命为120 s，寿命提高20%。2) 在节点比例和部署节点数都相同的条件下，较之其他算法，本文提出的ECRO算法表现最好，验证了改进算法的优越性。
表 4 节点构成比例表
情况 类型1节点 类型2节点 类型3节点 1 1/3 1/3 1/3 2 1/5 3/5 1/5 
图 6 不同节点构成比例下网络寿命的比较
-
本文提出了一种基于增强珊瑚礁算法的网络寿命最大化策略，解决应用场景中监测目标差异化的监测要求和网络连通条件下异构有向传感器节点调度的问题。相比现有的节点调度算法，本文研究问题的特色在于，节点异构、监测目标差异化监测和网络连通的要求更加符合有向传感器网络部署的实际情况。未来将应用本文提出的方法研究三维空间内的异构有向传感器网络节点的覆盖连通调度问题；另外在网络连通方面，将引入中继节点实现网络多跳连通，在此基础上研究更宽泛意义上的异构有向传感器网络连通覆盖调度算法，使得算法更具实用性。
Connected Coverage Scheduling Algorithm for Heterogeneous Directional Sensor Networks
-
摘要: 在面向目标监测的有向传感器网络中，为满足监测目标的不同监测要求，并保持网络连通前提下网络寿命最大化，提出了一种基于增强珊瑚礁算法的节点调度算法。受集合覆盖的启发，以增强珊瑚礁算法为工具求解满足连通覆盖要求的集合。增强珊瑚礁算法采用SOBOL序列和反向学习策略对种群进行初始化，同时在非性繁殖过程中，借鉴和声搜索、生物地理学算法和自适应变异策略的差分进化算法达到继承种群的优秀解和增强子代的优化能力的目的。再者，对种群的最差个体执行随机反向学习和与最优个体差分策略以提升最差个体的优化能力。在数值测试以及在传感器网络节点调度方面的仿真结果表明，改进珊瑚礁算法的性能优于其他算法，证明了改进算法的有效性。Abstract: A node scheduling algorithm based on enhanced version of coral reef optimization algorithm (shortly for ECRO) is proposed to solve the life maximization problem of heterogeneous directional sensor networks for connectivity and differentiated target coverage requirements. Based on cover sets theory, ECRO is utilized to get the cover sets, which can cover all the targets and satisfy their connectivity and coverage quality requirements. The improvement of coral reef optimization (shortly for CRO) lies in the three aspects. Firstly, the population is initialized by the SOBOL sequence and an opposition learning strategy. Secondly the operator of harmony search algorithm, immigration in biogeography-based optimization and a self-adaptive mutation strategy in differential evolution algorithm are introduced into the brooding procedure of the coral larvae formation to conserve the excellent solutions of the population and enhance the diversity of the descent and the ability of optimization for coral reef. Moreover, an opposition learning strategy and differential strategy with the optimal individual are utilized to improve the performance of the worst individual of the population. Extensive simulation experiments both in numerical benchmark functions and node scheduling are conducted to validate the proposed ECRO. The results show that the proposed ECRO outperforms the compared algorithms, which demonstrate the superiority of the proposed algorithm ECRO.
-
表 1 测试函数具体信息
测试函数 函数表达式 定义域 F1 ${f_1}(x) = \displaystyle\sum\limits_{i = 1}^n {{x^2}(i)} $ $x(i) \in [ - 100,100]$
F2${f_2}(x) = {\displaystyle\sum\limits_{i = 1}^n {(\displaystyle\sum\limits_{j = 1}^i {x(j))}^2 } }$ $x(i) \in [ - 100,100]$
F3${f_3}(x) = \displaystyle\sum\limits_{i = 1}^n {(\left\lfloor {x(i) + 0.5} \right\rfloor } {)^2}$ $x(i) \in [ - 100,100]$ F4 ${f_4}(x) = \displaystyle\sum\limits_{i = 1}^n {\left| {x(i)} \right|} + \prod\limits_{i = 1}^n {\left| {x(i)} \right|} $ $x(i) \in [ - 100,100]$ 
下载: 导出CSV
表 2 结果比较
测试函数 算法 最佳结果平均值 最佳结果方差 F1 GA
SA
DE
LADE
CRO
EHS
ECRO3.69×10−4
1.21×10−4
5.91×10−5
4.39×10−5
5.24×10−5
4.01×10−5
1.35×10−64.30×10−4
1.36×10−4
1.35×10−4
1.04×10−4
1.09×10−4
1.00×10−4
1.03×10−6F2 GA
SA
DE
LADE
CRO
EHS
ECRO1.09×10−3
1.56×10−5
1.12×10−4
2.26×10−5
2.38×10−5
1.96×10−5
1.13×10−68.90×10−4
2.20×10−5
1.04×10−4
1.59×10−5
1.61×10−5
1.46×10−5
1.09×10−6F3 GA
SA
DE
LADE
CRO
EHS
ECRO3.74×10−2
6.10×10−6
0
0
0
0
03.48×10−2
6.44×10−6
0
0
0
0
0F4 GA
SA
DE
LADE
CRO
EHS
ECRO2.86×10−2
6.27×10−3
3.90×10−3
5.77×10−4
5.84×10−4
4.96×10−4
3.69×10−62.08×10−2
4.76×10−3
3.15×10−3
6.97×10−4
7.08×10−4
6.37×10−4
6.91×10−6
下载: 导出CSV
表 3 节点参数表
类型 感知
半径/m通信
半径/m感知
角度$ {\theta }_{i} $ 节点
能量/J每个工作周期
消耗能量/J节点
数量1 10 20 ${{\text π} \mathord{\left/ {\vphantom {{\text π} 3}} \right. } 3}$ 100 0.1 10 2 20 40 ${{2{\text π} } \mathord{\left/ {\vphantom {{2{\text π} } 3}} \right. } 3}$ 200 0.5 10 3 15 30 $ {{\text π} \mathord{\left/ {\vphantom {{\text π} 2}} \right. } 2} $ 150 0.3 10
下载: 导出CSV
-
[1] MA X Y, YI P, CHEN J. Distributed gradient tracking methods with finite data rates[J]. Journal of Systems Science and Complexity, 2021, 34(5): 1927-1952. doi: 10.1007/s11424-021-1231-9 [2] ZHAI C, ZHANG H T, XIAO G X, et al. Design and assessment of sweep coverage algorithms for multiagent systems with online learning strategies[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 25(11): 1-12. [3] HU J P, WU Y Z. Interventional bipartite consensus on coopetition networks with unknown dynamics[J]. Journal of the Franklin Institute, 2017, 354(11): 4438-4456. doi: 10.1016/j.jfranklin.2017.04.010 [4] HU J P. On robust consensus of multi-agent systems with communication delays[J]. Kybernetika, 2009, 45(5): 768-784. [5] 王洁, 王瑞欣, 范兴刚, 等. 一种连通有向传感器网络的目标覆盖增强算法[J]. 浙江工业大学学报, 2021, 49(6): 623-628, 663. doi: 10.3969/j.issn.1006-4303.2021.06.005 WANG J, WANG R X, FAN X G, et al. A probabilistic target coverage enhancing scheme in connecting DSN[J]. Journal of Zhejiang University of Technology, 2021, 49(6): 623-628, 663. doi: 10.3969/j.issn.1006-4303.2021.06.005 [6] ALIBEIKI A, MOTAMENI H, MOHAMADI H. A new genetic-based approach for solving k-coverage problem in directional sensor networks[J]. Journal of Parallel and Distributed Computing, 2021, 154: 16-26. doi: 10.1016/j.jpdc.2021.03.006 [7] TA A S, THI H A L, DINH T P. Solving efficient target-oriented scheduling in directional sensor networks by DCA[C]//The 6th International Conference on Computer Science, Applied Mathematics and Applications (ICCSAMA). [S. l.]: Springer, 2019, 1121: 52-63. [8] MOHAMADI H, SALLEH S, RAZALI M N. Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges[J]. Journal of Network and Computer Applications, 2014, 46: 26-35. doi: 10.1016/j.jnca.2014.07.038 [9] BAKHT A J, MOTAMENI H, MOHAMADI H. A learning automata-based algorithm for solving the target k-coverage problem in directional sensor networks with adjustable sensing ranges[J]. Physical Communication, 2020, 42: 1-11. [10] ALIBEIKI A, MOTAMENI H, MOHAMADI H. A new genetic-based approach for maximizing network lifetime in directional sensor networks with adjustable sensing ranges[J]. Pervasive and Mobile Computing, 2019, 52: 1-12. doi: 10.1016/j.pmcj.2018.10.009 [11] 李明, 林新宇. 基于集合覆盖的异构有向传感网寿命优化策略[J]. 重庆工商大学学报(自然科学版), 2021, 38(1): 14-20. LI M, LIN X Y. Life maximization strategies based on cover sets for heterogeneous directional sensor networks[J]. Journal of Chongqing Technology and Business University (Natural Science Edition), 2021, 38(1): 14-20. [12] 李明, 胡江平. 异构传感器网络中基于差分进化的调度算法[J]. 计算机工程, 2019, 45(9): 70-75. LI M, HU J P. Scheduling algorithm based on differential evolution in heterogeneous sensor network[J]. Computer Engineering, 2019, 45(9): 70-75. [13] AMMARI H M. Connected k-coverage in two-dimensional wireless sensor networks using hexagonal slicing and area stretching[J]. Journal of Parallel and Distributed Computing, 2021, 153: 89-109. doi: 10.1016/j.jpdc.2020.12.008 [14] KABAKULAK B. Sensor and sink placement, scheduling and routing algorithms for connected coverage of wireless sensor networks[J]. Ad Hoc Networks, 2019, 86: 83-102. doi: 10.1016/j.adhoc.2018.11.005 [15] YU C S, SHIN K G, LEE B. Power-Stepped protocol: Enhancing spatial utilization in a clustered mobile ad hoc network[J]. IEEE Journal on Selected Areas in Communications, 2004, 22(7): 1322-1334. doi: 10.1109/JSAC.2004.829349 [16] SALCEDO S S, GALLO M D, PASTOR S A, et al. Offshore wind farm design with the coral reefs optimization algorithm[J]. Renewable Energy, 2014, 63(2): 109-115. [17] LI M, MIAO C Y, LEUNG C. A coral reef algorithm based on learning automata for the coverage control problem of heterogeneous directional sensor networks[J]. Sensors, 2015, 15: 30617-30635. doi: 10.3390/s151229820 [18] BRATLEY P, FOX B L. Implementing sobols quasirandom sequence generator (algorithm 659)[J]. ACM Transactions on Mathematical Software, 2003, 29(1): 49-57. doi: 10.1145/641876.641879 [19] SIMON D. Biogeography-based optimization[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(6): 702-713. doi: 10.1109/TEVC.2008.919004 [20] 李明, 曹晓莉, 胡卫军. 基于多目标和声搜索的无线传感器网络分簇路由算法[J]. 仪器仪表学报, 2014, 35(1): 162-168. LI M, CAO X L, HU W J. Optimal multi-objective clustering routing protocol based on harmony search algorithm for wireless sensor networks[J]. Chinese Journal of Scientific Instrument, 2014, 35(1): 162-168. [21] ISHIBUCHI H, MURATA T. A multi-objective genetic local search algorithm and its application to flowshop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 1998, 28(3): 392-403. doi: 10.1109/5326.704576 [22] 李明, 胡江平. 复杂条件下移动异构无线传感器网络覆盖算法[J]. 传感器与微系统, 2019, 38(12): 124-127,132. LI M, HU J P. Coverage algorithm for mobile heterogeneous WSNs under complex conditions[J]. Transducer and Microsystem Technologies, 2019, 38(12): 124-127,132. -
点击查看大图
图(6) / 表(4)
计量
- 文章访问数: 3625
- HTML全文浏览量: 1046
- PDF下载量: 54
- 被引次数: 0
