无线传感器网络双准则优化:链路调度与能量消耗

抽象的

链路调度对于无线传感器网络中可靠的数据通信非常重要。以前的作品主要关注如何找到最小调度长度但忽略能量消耗的影响。在本文中，我们将它们整合在一起并通过多目标遗传算法来解决它们。作为一种贡献，通过联合建模路由选择和无干扰链路调度问题，我们对链路调度和能量消耗之间的关系进行了系统分析。考虑到WSN的具体多对一通信性质，我们提出了一种基于NSGA-II的新的链路调度方案（非主导排序遗传算法II）。我们的方法旨在搜索满足无线传感器网络的最小调度长度和能量消耗的最佳路由树。为了实现这一目标，基于路由树的解决方案表示，基于树的重组和突变包括基于树的重组和突变的遗传操作以及基于启发式链路调度算法的适应性评估。广泛的仿真表明，我们的算法可以快速收敛于两个性能度量之间的Pareto最佳解决方案。

1.介绍

无线传感器网络通常由大量具有传感、数据处理和通信组件的微小传感器节点组成。一般来说，它是由这些传感器节点以自组织的方式形成的[1］.近年来，无线传感器网络在医学、太空探索、火山监控、智能应用、入侵检测、边境监控等诸多应用领域发挥着越来越重要的作用[2，3.］.

MAC接入是无线传感器网络设计的关键问题之一[4］.许多性能指标，如网络生命周期、信息感知的准确性、传输延迟、位置准确性等，都与MAC技术密切相关[5］.一般来说，CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)和TDMA (Time Division Multiple Access)是两种广泛应用于无线网络的MAC接入技术[6］.对于前者，由于其信道接入模式的竞争性，无法支持接入公平性。此外，该技术中应用的一些策略，如空闲信道侦听、通信冲突避免等，会消耗额外的能量，无法满足大规模应用的需求。而在基于TDMA的MAC接入技术中，通过为每个无线终端分配时隙，可以消除冲突，保证定时接入的链路带宽，为无线传感器网络提供更可靠的数据传输。此外，TDMA协议中的传感器节点在未分配时隙的情况下，可以低占空比运行，从而节省能源，延长网络生命周期[7］.例如，在流量监控应用中，使用TDMA技术的传感器节点的生命周期为1,200天，而使用CSMA/CA技术的传感器节点的生命周期为10天[8］.

如何有效地分配时隙以满足各种路由要求是设计无线传感器网络时分多址调度的主要任务。由于调度周期的数量有限，一些相邻的传感器节点可以通过随机的时隙分配方式分配到同一时隙。这将导致干扰和容量降低。因此，需要设计无干扰链路调度算法。此外，由于传输时延与调度周期有关，所以调度周期越长，传输时延越大。因此，TDMA调度算法应该尽量减少所需的时隙数量。此外，由于各传感器节点电池的功率受限，还应考虑能耗优化的链路调度算法，以延长网络生存时间。

最近，无线网络的链路调度受到了广泛的关注[9- - - - - -12］.由于无线冲突可以被建模为干扰（冲突）图[9，10]假设每个节点具有相同的数据包到达率，有些作品使用基于图形的启发式算法[11，12]来寻找无干扰链路调度方案。但是，由于WSN的中继特性，每个传感器节点既要传输自己的数据包，又要转发其子节点的数据包;因此，上述具有相同时隙需求的调度机制不能直接应用于WSN应用。文中分析了无线多跳网络中寻找无干扰链路调度方案的时间复杂度。13，给出了多项式时间复杂度的图着色解。为了减少获取整个网络拓扑所带来的消息负载，文献[14，15]提出了一种基于局部拓扑的分布式调度机制。然而，这些调度算法都是基于网络之间存在一些独立的点对点路由会话的假设。在[16]，研究了线性占空比无线传感器网络的快速时隙分配问题，提出了集中式最优和分布式调度算法。然而，在传感器网络中，数据往往从一些传感器节点转移到一个汇聚节点;因此，不考虑具体的多对一通信性质。为此，一些文献将调度机制和路由机制结合起来设计。在[17]，采用AODV路由协议生成满足所有路由会话需求的多条路径，调度算法只在最优路由上执行。同样，文献[18首先使用存在的路由算法来确定每个节点的业务需求，然后遗传算法和粒子群算法杂交以找到最佳插槽分配。但是，路线优化不会以其方法考虑。在文献中[19[提出了基于树的链路调度算法与功率控制相结合，可以提高通信可靠性以及减少数据收集延迟。在文献中[20.]，建立了包括物理层、MAC层和网络层问题的跨层优化模型，并提出了凸优化方法。在[21]，研究了收敛cast路由树的链路调度问题，提出了一种与信道分配相结合的时隙分配算法。但是，以上讨论的这些算法没有考虑能量消耗，容易导致网络生存时间比预期的要短。

本文的原始贡献如下所示：首先，我们制定了传感器网络调度问题的联合优化，包括路由选择和能耗作为多目标优化问题。其次，通过将特定的多对一路由树作为进化的个人编码，我们提出了一种基于NSGA-II的新型链路调度方案（非主导的分类遗传算法II）。第三，通过给定的路由树和链路插槽要求，我们提出了一种启发式插槽分配算法来评估每个人的适应性。最后，我们进行了广泛的模拟，以证明我们提出的方法的有效性。本文的其余部分安排如下。部分2介绍假设、网络模型和设计注意事项。本节提出了基于NSGA-II的链路调度算法3.．部分4给出了仿真结果5结束了我们的论文。

2.网络模型与问题表述

２.１.网络模型

假设一个无线传感器网络由单个汇聚节点和组成以不同速率周期性地生成数据的传感器节点。汇聚节点和传感器节点的标识为．不损失普遍性，网络中的每个节点都有一个固定的通信半径．整个网络可以用一个有向拓扑图来表示， 在哪里为节点的集合，有向边集，和表示节点之间的距离和．由于无线无线电的广播传输特性，在干扰范围内的一对节点即使不能直接通信，也可能相互干扰对方的通信。要调度两个环节同时的时隙，必须保证调度会避免干扰。文献中引入了两种不同类型的干扰，即初级干扰和次级干扰[22]，如图所示1．

如图所示，当节点同时发送和接收数据包时，会发生主干扰1(一)，1 (b),1 (c)．发射机-发射机(t-t)干扰是由于在同一台接收机上的两个并行传输相互干扰而引起的，而单个发射机不能将发给两个不同接收机的数据包分开，这将导致接收机-接收机(r-r)冲突;发送-接收(t-r)冲突的发生是因为节点不能同时发送和接收。二次干扰，如发射机-接收机-发射机(t-r-t)干扰模型，当一个节点接收到两个或多个独立的传输，但只有一个传输是针对该节点的，如图所示1 (d)．这里，我们应该注意到另外的辅助干扰模型，接收器 - 发射器 - 接收器（R-T-R）干扰模型可能在802.11协议中导致RTS / CTS握手中的不必要的传输延迟。但是，在基于TDMA的MAC协议中，通过为每个链路分配不同的时隙，不存在R-T-R冲突。

我们雇佣了一个矩阵表示中所有链接的链接时间表， 在哪里是插槽总数和链接总数在吗．为每个元素在矩阵,我们有

让表示将引起干扰的链路集．为了实现无冲突调度，应将这些相互干扰链路分配给不同的时隙，我们有

定义作为路由会话，其中和代表源传感器节点和会话的插槽需求,分别。定义随着交通的流动来（和从来)会话在槽，我们有

什么时候，，则得到

为了实现无冲突调度，我们有

让表示端到端的路由会话，到沉没节点，在哪里分别表示源传感器节点及其槽位需求。定义从节点出发的流节点（来自节点节点)会话， 在哪里．路由约束可以定义为: (在哪里6)表示除源节点和汇聚节点外，所有槽位的流入流量等于每个节点的流出流量;（7)表示该源所有槽位的流出流量等于其流量需求;（8)表示汇聚节点各槽位的流入流量等于汇聚节点的流量需求;和(9）指出，所有遍历链接的所有会话的流量都不能超过此链接上的总分配插槽。

以调度周期为基础,变量以及会话路由路径的长度，可以计算为

假设能量消耗仅由通信成本主导，而不是传感和处理成本。一个传感器消耗在一个槽中发送数据时的能量单位，当它耗尽时在一个槽中接收数据时的能量单位。如果我们忽略汇聚节点消耗的能量，那么，对于每个路由会话，给定它的路由路径长度，其能耗可计算为

数字2给出了节点a向汇聚节点传输1单位感知数据时网络能耗的简单示例。根据图2，则可以得到路由路径的长度为3。基于(11），路线必须发送数据3次并接收两次;我们可以获得这条路线的总能耗．

２.２.问题公式化

现在我们准备定义联合优化问题:给定拓扑图以及路由会话的数量，我们的目标是找到一种满足所有路由要求的无干扰链路调度方案，并使调度长度和总能耗最小。形式上，该问题可以表示为以下多目标问题: 在哪里输入参数。请注意,和为优化变量，用于确定网络槽位分配和路由选择。按照惯例，优化问题的形式为bicriteria-objective整数规划(MOIP)问题，NP-hard [13， CPLEX是不能解决的。在下一节，我们将开发一个基于NSGA-II的嵌套优化框架来解决这个问题。

3.基于NSGA-II的多目标优化

在本节中，我们首先简要介绍了多目标优化的基本原理。然后，我们基于NSGA-II的方法描述了我们的方法。可以给出多目标优化的数学描述 在哪里是拖把的解决方案和客观函数的数量．受等式和不等式约束的可行集是否记为和以及显式变量边界．在多目标极小化问题中，给出了一个解主宰另一个解决方案（）如果并且只有

针对这类多目标优化问题，给出了求解方法称为帕累托最优解，当且仅当没有占据主导地位．用于解决MOP的众所周知的技术是加权方法，其将原始拖布转换为单个优化问题，以形成目标的线性组合 在哪里，表示重量目标是．通常情况下,和．然而，加权法在求解MOP时主要有两个缺点[23］.首先，它无法在带有非凸普罗托最佳前线的拖镜中找到帕累托最佳解决方案，这可能会减少设计替代品的数量。如图所示3.，赋权法只能找到A点和D点的Pareto最优解;而其他三个解B、C、E都找不到。其次，需要先验地为每个优化函数选择合适的权值;在生成解决方案之前，用户可能不会清楚关于首选项的决定。

近年来，多目标遗传算法被认为是解决多目标优化问题的较好算法。与加权法相比，MOGA可以在一次运行中捕获多个Pareto最优解，并通过遗传操作挖掘解的相似性。此外，MOGA对帕累托最优锋的连续性形状影响较小。因此，在本文中，我们采用了目前研究最广泛的MOGA，非支配排序遗传算法II (NSGA-II) [24，求帕累托最优解。

MOGA算法不能直接处理优化问题的变量。他们用类似染色体的密码来表示解决方案。因此，第一个问题是如何表示问题的解决方案，即如何使用适合该问题的数据结构[25］.从描述中描述的优化问题的描述12)，我们可以注意到优化问题的难点在于确定路由树。具体来说，如果通过一些技术可以得到路由树，那么也可以得到能耗。因此，在本文中，我们使用路由树作为问题的表示。在这种表示中，每个路由会话的路径被编码为一个正整数字符串。因为有路由路径和多对一通信性质，这些路由路径进一步组合到反向组播树，并表示为整数阵列，其中一行列出路由的节点id水槽节点。数字4举例说明3条路由路径及其染色体表示，其中汇聚节点表示为节点0。为了探索遗传多样性，路由路径为任何路由会话是随机生成的。对于每个源节点，我们首先随机选择一个节点从，邻居．然后我们随机选择一个节点从．重复这个过程，直到到达汇聚节点。因此，我们得到一个随机路径．由于反向组播树不允许循环，因此应该排除已经包含在反向组播树中的节点，从而避免同一节点重新进入。

通常，MOGA从初始群体开始，初始群体由随机生成的信道分配方案。此初始群体将执行选择，交叉和突变运算符，以在搜索空间中生成新个人。对于人口中的每个信道分配方案，即个人，适用适用性值以反映解决问题的善等。在遗传演化的每个循环期间，具有更好的健身值的染色体将在随后的几代存活的可能性更高，在自然界中效仿最适合的生存现象。因此，设计MOGA中的第一个重要方面是如何计算个体的健身。在我们的算法中，适合度被定义为最低调度周期和总能耗。当路由树在染色体中表示时，我们可以计算所有路由路径的总长度。因此，可以直接计算染色体的总能量消耗。由于找到了具有给定染色体表示的最小调度期是NP-HARD [14]，提出了一种基于启发式的适应度评估链路调度算法，如算法所示1．

从算法1，可以看出我们的启发式链路调度算法主要包括链路调度顺序选择和时隙分配两部分。在链路调度顺序选择部分，干扰程度最小的链路优先服务，如第(2)~第(6)行所示。在槽位分配部分，我们首先在调度周期内分配尽可能多的槽位满足其对每条被服务链路的槽位需求，如(8)至(16)所示;如果我们不能分配足够的插槽来满足它的插槽需求，网络的调度周期会更新吗将分配给此链接，可以以行（17）到（20）显示。

交叉和突变是GA的演化过程中涉及的另外两个其他基本操作。交叉操作的目的是通过对亲本染色体进行某些遗传重组来产生后代染色体（新个体）。这些后代染色体与他们的父母共享遗传相似之处，而是从不同的一代中享有遗传相似之处。关于交叉操作，考虑到染色体通过树数据结构表示，我们采用单点交叉来交换部分染色体，如图所示5．两个染色体和交叉时，首先在同一来源节点(节点7)的这两条染色体之间找到至少一个共同节点(节点11)，然后再找到一个共同节点，记为，是随机选择的。例如,在，有一条路径由两部分组成:()和(）.在，也有一条由两部分组成的路径:()和(）.交叉操作然后交换路径()和(）交叉概率．在进行交叉操作后，种群将进行变异操作。突变概率每次我们选择一条染色体其中一个源节点是随机选择的。在路上()选取一个节点作为突变点，记为．突变将取代路径（）通过一个新的随机路径。由于交叉和突变后的新生成的染色体可能是不可行的，因此将执行额外的修复执行，以消除循环的额外修复执行，这可以有助于加快收敛。

与传统的GA不同，NSGA-II是建立在各个方面的非支配地位之上的。种群中的每个个体被分配两个适应度评估(调度长度和能源消耗)。此外，如果两个解具有相同的适应度值，则进一步用拥挤距离来度量，拥挤距离可以通过其相邻解沿每个目标的距离来计算(见[24]详情)。算法2描述了NSGA-II链路调度算法的详细过程。从算法2，我们可以看到在生成初始人口后(如步骤1所示)，首先执行快速非支配排序操作，以生成初始代的非支配前沿，如步骤2所示。然后，将初始种群与新生成的种群相结合，执行受控的精英主义操作，可进行更新通过从第一前面开始选择解决方案。如果剩余允许前线的解决方案数大于人口中的可用位置，则首先选择具有较大拥挤距离的解决方案。这些程序可以在步骤3中看到。最后，类似于链接GA，交叉和突变操作也应用于产生新的人群，如步骤4所示。经过几次迭代，整个种群只包含帕累托最优前沿附近或在帕累托最优前沿的解。

4.绩效评估

在本节中，我们将给出我们的算法的仿真结果。所有的仿真都在Matlab 7.0中执行。引入总能耗和调度长度两个指标来评价算法的性能。对于所有的仿真，我们设置了接收和发送一个单元数据的能量消耗和分别为1和2。人口的大小设定为100;交叉概率和突变概率设置为0.9和0.1。控制精英主义设置为0.5。在我们的仿真中，我们采用了两种节点分布:随机分布和热点分布，如图所示6．在随机分布中，所有节点随机分散在目标区域，而在热点分布中，所有节点随机分散在高斯分布中。

首先，随机部署50个节点目标区域，如图所示9．水槽节点（带ID 37）位于该区域的中心。传输范围和干扰范围每个传感器节点等于20。假设每个传感器节点具有路由到宿节点的单位插槽需求。数字7给出随机生成总体的初始解分布。数字8显示运行多个世代算法后获得的Pareto最佳解决方案。从数字7和8，我们可以看到30代后发现了更多的不合适的解决方案。经过600代之后，我们可以找到具有最小调度长度和能量消耗的帕累托最佳解决方案。数字9显示上一代路由树的拓扑图，其中每条链路旁边的编号为链路号。各链路最终的槽位分配如表所示1．从路由树的描述和插槽分配中，我们可以得出结论，路由树中的任何相互干扰链路被分配不同的时隙，分配给任何链接的插槽总数也满足其路由要求，其演示了算法的有效性。

此外，我们在各种节点密度下测试我们的算法的性能，并比较所提出的算法与现有路由树的性能结合在[中提出的链路调度算法14］.比较用不同的节点密度执行，其中传感器节点的数量从10增加到100.对于每个部署，我们已经生成了10个实例并在每个独立测试中应用了我们的算法。随机热点分布的仿真结果如图所示10和11，它记录了这20次测试的平均溶液。在这个仿真中，我们的算法结合了路由树的生成和链路调度算法。由于在[中没有考虑路由优化14]，首先分别用Dijkstra算法和MST算法生成路由树，然后对给定的路由树应用调度算法。如图所示10和11，很明显，可以看出更多的流量负荷导致调度时期和能量消耗的增加。我们还可以看出Dijkstra路由算法可以实现最小化的能量消耗，这主要是因为当应用Dijkstra路由算法时，可以实现路由树的最小化长度。但是，Dijkstra路由算法的路由树中的最大节点度导致调度周期最长。与上述两种算法相比，我们的算法可以实现最短的调度周期，并且能量消耗与Dijkstra路由算法的能耗几乎相同，而不管节点分布如何，这进一步证明了我们算法的有效性。

5.结论与未来工作

本文研究了无线传感器网络链路调度和能量消耗的联合优化问题。将路由选择和链路调度结合起来，对无线传感器网络的能量消耗和链路调度进行了分析，并将其定义为bicriteria-objective整型问题．针对无线传感器网络的多对一特性，我们提出了一种基于NSGA-II的高效优化方案。为了保证问题的个体有效性和快速收敛，设计了基于路由树的表示方案以及相应的交叉和变异规则来满足问题中的约束条件。通过大量的仿真，我们证明了基于NSGA-II的优化框架在求解复杂的多目标传感器网络设计模型方面是很有前景的。

利益冲突

提交人声明没有关于本文的出版物的利益冲突。

致谢

基金资助:国家自然科学基金资助项目(no. 20141201);61402096,没有。61173153,没有。中央高校基本科研业务费资助项目(N110318001、N130504007、N140407001)。

参考

1. 王旭东，《无线网状网络:一项调查》，计算机网络，卷。47，没有。4，pp。445-487，2005。视图:出版商的网站|谷歌学术
2. 王宁，王刚，余东，“无线自组织和传感器网络中连接主导集的综合研究”，电脑通讯第36卷第2期2，页121-134,2013。视图:出版商的网站|谷歌学术
3. 贾建军，吴旭东，陈建军，王旭东，“移动传感器网络线路障碍覆盖的自主重部署算法”，国际自组织和泛在计算杂志，第16卷，第5期。1，页58-69,2014。视图:出版商的网站|谷歌学术
4. I. Rhee, a . Warrier, M. Aia, J. Min, M. L. Sichitiu，“Z-MAC:无线传感器网络的混合MAC”，网络上的IEEE / ACM事务，第16卷，第5期。3，第511-524页，2008。视图:出版商的网站|谷歌学术
5. 张国光，贾建军，“道路传感器网络的分布式定位:一种博弈论方法，”工程数学问题，第640391号，9页，2013。视图:出版商的网站|谷歌学术|MathSciNet
6. S. Gandham，Y. Zhang和Q. Huang，“无线传感器网络中的换换时间 - 最佳调度”，计算机网络，卷。52，不。3，pp。610-629，2008。视图:出版商的网站|谷歌学术
7. M. Arifuzzaman，M. Matsumoto和T.Sato，“一个智能混合MAC，具有基于流量分化的无线传感器网络的QoS”，IEEE传感器杂志，卷。13，不。6，pp。2391-2399,2013。视图:出版商的网站|谷歌学术
8. S. C. Ergen和P. Varaiya，“PEDAMACS:传感器网络的功率效率和延迟感知媒体接入协议”，IEEE移动计算机上的交易，卷。5，不。7，pp。920-930,2006。视图:出版商的网站|谷歌学术
9. “干扰对多跳无线网络性能的影响”，中华人民大学学报(自然科学版)第9届移动计算和网络国际会议的诉讼程序（Mobicom'03），第66-80页，ACM, 2003年9月。视图:谷歌学术
10. G. Sharma, R. Mazumdar，和N. Shroff，“关于无线网络调度的复杂性”，在年度移动计算与网络国际会议的诉讼程序（Mobicom'06），第227-238页，ACM，纽约，纽约，美国，2006。视图:谷歌学术
11. T. Salonidis和L. Tassiulas，“用于无线临时网络的端到端速率保证的分布式动态调度”第六届ACM移动自组网与计算国际研讨会论文集(MOBIHOC’05)，第145-156页，ACM, 2005年5月。视图:出版商的网站|谷歌学术
12. E. Uysal-Biyikoglu, B. Prabhakar和a . El Gamal，“通过无线链路的节能分组传输”，网络上的IEEE / ACM事务，第10卷，第5期。4，页487-499,2002。视图:出版商的网站|谷歌学术
13. S. C. ergen和P.Varaiya，“无线传感器网络的TDMA调度算法”无线网络，第16卷，第5期。4, pp. 985-997, 2010。视图:出版商的网站|谷歌学术
14. V. Rajendran, K. Obraczka, J. J. Garcia-Luna-Aceves，“无线传感器网络的节能、无碰撞介质访问控制”第一届嵌入式网络传感器系统国际会议论文集(SenSys’03)，pp.181-192，ACM，2003年11月。视图:谷歌学术
15. 李志强，李志强，“无线自组织网络的分布式随机时分多址调度”第七届ACM移动Ad Hoc网络与计算国际研讨会论文集(MobiHoc '06)，第190-201页，ACM, 2006年5月。视图:谷歌学术
16. Z.沉，H.江和Z. Yan，“线性循环无线传感器网络中的快速数据收集”，IEEE车辆技术汇刊，第63卷，第2期第4页，1951-1957,2014。视图:出版商的网站|谷歌学术
17. 刘s.，冯绍峰，叶伟，庄辉，“基于IEEE 802.16无线mesh网络的集中式调度算法，”电脑通讯，第32卷，第2期5，第943-953页，2009。视图:出版商的网站|谷歌学术
18. J.Mao，Z.Wu和X.Wu，“TDMA调度方案，无线传感器网络中多对一通信”，“电脑通讯，第30卷，第2期4，页863-872,2007。视图:出版商的网站|谷歌学术
19. D.龚和Y. yang，“基于低延迟的SINR基于无线传感器网络的数据，”IEEE无线通信汇刊，卷。13，不。6，pp。3207-3221,2014。视图:出版商的网站|谷歌学术
20. 崔淑娟，“基于小尺度传感器网络的跨层能量和延迟优化”，IEEE无线通信汇刊，第6卷，第2期10, pp. 3688-3699, 2007。视图:出版商的网站|谷歌学术
21. O. Durmaz Incel, A. Ghosh, B. Krishnamachari，和K. Chintalapudi，“基于树的无线传感器网络的快速数据收集”，IEEE移动计算机上的交易，卷。11，不。1，pp。86-99,2012。视图:出版商的网站|谷歌学术
22. P. Djukic和S. Valaee，“延迟了多跳TDMA无线网络的感知链接调度”，网络上的IEEE / ACM事务，卷。17，不。3，PP。870-883，2009。视图:出版商的网站|谷歌学术
23. “非线性多准则优化问题中Pareto曲面生成的一种新方法”，暹罗期刊优化，第8卷，第2期3，第631-657页，1998。视图:出版商的网站|谷歌学术|MathSciNet
24. K. Deb, A. Pratap, S. Agarwal，和T. Meyarivan，“一种快速和精英的多目标遗传算法:NSGA-II，”IEEE进化计算汇刊，第6卷，第2期2，页182-197,2002。视图:出版商的网站|谷歌学术
25. “基于多目标遗传算法的无线传感器网络能量覆盖控制”，“基于多目标遗传算法的无线传感器网络能量覆盖控制”，计算机与数学应用，卷。57，没有。11-12，PP。1756-1766,2009。视图:出版商的网站|谷歌学术|MathSciNet

版权

版权所有©2015 Jian Chen等。这是分布下的开放式访问文章知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。