司恩波, 王　晶, 靳其兵, 周靖林

(北京化工大学 信息科学与技术学院,北京 100029)



工业无线网络链路选择与时隙分配的同步优化

司恩波, 王晶, 靳其兵, 周靖林

(北京化工大学 信息科学与技术学院,北京 100029)

摘要:以工业无线网络为研究对象,通过结合多链路路由算法和时隙调度算法静态优化无线网络的传输性能.链路选择用于优化网络的空间资源,时隙分配用于优化网络的时间资源,两者相互作用影响无线网络的传输性能.根据无线网络的传输特性给出多跳分级的无线网络模型,将分布式的工业无线网络系统层次化,减小无线网络节点之间联通的复杂性,并给出基于该模型的无线网路链路选择和时隙分配同步优化架构.针对这2个分属于空间和时间上的不同问题,采用链路染色方法进行标记,避免网路传输链路冲突问题；采用遗传算法隐并行性和组合优化解决链路选择和时隙分配的相互干扰；提出层次化的编码方案,并给出基于遗传算法双层编码方案使2类问题得以结合；给出基于遗传算法的同步优化策略并加以验证.实验结果表明：优化后的算法使得无线无线网络的采样率、数据平均延迟和节点负载性都得到进一步的提升.

关键词：WIA-PA无线标准；多跳分级模型；同步优化；遗传算法；双层编码；链路选择；时隙分配

伴随着控制技术、微机技术、传感器技术和通信技术的发展,无线传感器网络愈来愈成熟,功能越来越稳定.工业无线控制网络是在无线传感器网络的基础上发展起来的,是无线传感技术在工业领域的应用和扩展.时分多址(timedivisionmultipleaccess,TDMA)信道接入机制是工业无线网络使用的信道接入机制之一.在TDMA机制中,如何为存在冲突的链路分配不同的时隙,即时隙分配问题,一直是工业无线网络的研究热点,是属于NP难的问题[1].

目前关于TDMA机制下的工业无线网络时隙分配的研究大多都是在确定的链路上通过时隙的分配来优化网络的采样率、数据延迟和电池消耗等,很少有针对整体网络的优化.图染色算法是其中一种局部优化算法[2-4].图染色算法通过给网络上的不同链路染色,使有冲突的链路染上不同的颜色,再为不同的颜色分配相应的时隙,保证数据在网络中传输不会遇到冲突问题；但是没有考虑到链路传输数据的时间顺序会影响数据传输的实时性能.文献[5]的研究考虑了时隙顺序对网络性能的影响,但只是以节点距网关的远近作为发送顺序的评判标准.Sridharan等[6]提出一种线性规划模型和相应的TDMA调度算法,使用该算法来提高网络的公平性并减少数据传输时延.Gandham等[7]提出一种基于数据收集的分布式调度方案,但是该方案没有考虑节点间的干扰情况,数据传输时会产生冲突.Djukic等[8-10]的研究将TDMA时隙调度问题简化为网络冲突图上的数据流问题,并通过减小冲突的方法优化网络的平均延迟.Gobriel等[11]提出一种TDMA-ASAP(adaptiveslot-assignmentprotocol)自适应时隙分配协议算法,在保证TDMA机制高效率运行的前提下,使网络在低负载时保存设备的能量以提高无线设备的使用寿命,同时减少网络的延迟.针对有不均匀通信范围的无线网络,Luo等[12]提出一种位置自适应最优化分布(optimallyrigidgeographicaladaptivefidelity,ORGAF)算法用以减少网络的能量损耗.在实现节能的过程中,Ma等[13]以无线网络提供的数据聚合功能为基础,提出一种睡眠调度算法,使无线设备在数据传输完毕后进入睡眠状态用以减少网络的节点能量消耗.Zhou等[14]提出通过物理干扰模型下的链路调度实现多跳无线网络的吞吐量优化.Kar等[15]提出一种在实现任意拓扑的无线网络的最优化吞吐量的情况下同时保证网络的延迟的算法.Khan等[16]用仿真器QualNetSimulator对基于IEEE802.15.4标准下的线形和树形拓扑结构网络进行仿真,测试不同拓扑下的丢包率和端到端的延迟.为了克服无线网络中存在的带宽不足及能耗过大等问题,有学者在无线干扰模型的基础上,将无线网络建模成图[17-18],从而将分布式的媒体访问控制(mediaaccesscontrol,MAC)调度问题转化为分布式图算法,例如极大独立集、图染色和支配集等算法.此外,还详细介绍了分布式图染色算法的研究进展,并在分布式顶点染色算法基础上,通过考虑节点度参数,提出了分布式MAC调度算法.

以上研究没有考虑链路与时隙之间的耦合影响,也没有平衡各节点之间的流量负载,容易造成个别节点流量过载,影响其传输性能.在以周期性数据为主的工业无线网络中,节点的负载仅与传输链路的选择有关,在保证不影响网络其他性能的前提下均衡网络的负载是一项重大的任务.链路选择和时隙分配并不是完全独立的2个问题,两者相互制约,共同影响着无线网络的性能,后续的操作会影响前面已经优化的目标的性能,因此两者需要进行同步优化.

本研究将链路的选择引入到无线网络的TDMA调度中,选择采样率、实时性能和节点负载作为无线网络的优化目标,根据工业无线网络的数据聚合和数据传输多跳特性,给出多跳分级的无线网络模型.以该模型为基础,使用链路染色算法消除网络的冲突,并提出链路-时隙双层编码的遗传算法以解决链路和时隙的相互干扰问题并优化整个网络的传输性能.

本文在分布式WIA-PA无线网络的基础上提出多跳分级的网络模型,并针对链路选择和时隙分配同步优化问题给出了网络整体架构和具体实现方案.考虑到链路选择和时隙分配分别属于空间域和时间域,同步优化非常困难,提出分布编码、同步优化的策略.最终通过仿真验证算法的有效性并对验证结果进行分析.

1WIA-PA无线网络的多跳分级模型

1.1WIA-PA网路结构及数据传输特性

本文以我国自主定义的WIA-PA无线网络为例来说明工业无线网络的架构,如图1所示.WIA-PA无线网络是一种混合拓扑结构的网络.网关和无线路由设备组成无线Mesh网络,Mesh网络服从网络管理器的集中式管理,网络中处于通信范围内的节点之间可以相互通信,不受到线缆的约束.本文只研究服从集中管理的WIA-PA的无线网络的Mesh结构.

图1　WIA-PA无线网络的结构Fig.1　Structure of WIA-PA wireless networ

无线网络中节点的通信距离和干扰距离决定节点间的数据传输行为.通信范围内的节点可以直接通信,通信范围外的节点只能通过中间节点进行间接通信.干扰范围是指节点在传输数据时会干扰到的区域,通常远大于节点的通信范围,如图2所示.

图2　节点的通信范围和干扰范围Fig.2　Communication range and inference range of nodes

中心节点在进行数据传输时会影响干扰范围内节点的数据通信.无线网络中节点的数据传输有以下几个特点：

1) 节点只能和通信范围内的节点进行直接的数据传输；

2) 节点一个时刻只可以执行一个动作(发送信号、接收信号或休眠),在执行发送或者接收信号时面向的对象只能是单个节点,不可以是多个节点；

3) 干扰范围内的几对节点在同时进行数据传输时需要使用不同的频率/信道.

1.2多跳分级的无线网络模型

本文把无线网络中一个节点向通信范围内的另一个节点传输数据的过程称为一跳,距离网关远的节点数据需要经过多跳才能到达网关.这里把数据从一个节点传输到达网关至少要经历的跳数称为这个节点的跳数级别.利用WIA-PA无线网络的多跳特性可以建立网络的多跳分级模型.

假设所有节点的通信距离均为DT,d(i,j)表示节点i和j之间的距离,那么当d(i,j)≤DT时,节点i和j在通信范围内,节点之间可以通过一跳进行数据传输.可以通过一跳到达的节点统称为该节点的邻居节点.通过推算网络节点的位置信息,可以得到整个网络的邻居节点矩阵A.设定网络中节点总数目为N,得到一个N×N的邻居节点矩阵A,用以描述网络中节点的邻居节点情况.矩阵的行和列均代表无线网络中的节点1～N,即i∈[1,2,…,N],j∈[1,2,…,N].矩阵元素为1,代表两节点是邻居节点,矩阵元素为0表示两节点不是邻居节点.显然,矩阵A是一个元素为0和1的对称矩阵：

以一个具有14个节点的小型无线网络为例来说明无线网络中节点的布局状况,如图3所示.图中,节点1表示网络网关,其他节点代表路由节点,虚线表示网络中存在的链路,在通信范围内的节点之间一定存在通信链路.

图3　工厂无线网络的节点布局图Fig.3　Layout of factory wireless nodes

根据图3可以得到每个节点的跳数级别和网络连接状态.由此提出一种多跳分级的无线网络模型,即将分布在不同位置但是拥有相同跳数级别的节点划分至同一层,由跳数级别低的层数向外一层一层扩展,将无规律的网络节点布局以层次化的形式表现出来,即可得到其多跳分级的无线网络模型,如图4所示.虚线的圆圈表示跳数的级别,最中心的圆圈表示一跳级别,跳数级别随着圆圈的外扩依此增加.可以看出一跳级别上有3个节点,二跳级别上有4个节点,三跳级别上有6个节点.由于图4中距离网关最远的节点需要三跳到达网关,这里节点最高的跳数级别是3.考虑更一般的情况,这里假设最高跳数级别为M,每个跳数级别g,g=1，2，…，M上有ng个节点,整个网络共有N个节点,则有

图4　WIA-PA无线网络多跳分级模型Fig.4　Multi-hops grading model of WIA-PA wirelessnetwork

工业无线网络可以通过连通图G(V,E)来简略表示,其中V表示网络节点的集合,E∈V*V是网络中所有节点间的链路的集合.链路是2个节点之间传输数据的路径,如：节点传输数据到节点的路径,即称之为节点i到节点j的链路,用e(i,j)表示.图4中从节点1到节点3、节点2到节点8的数据传输路径可以分别用e(1,3)和e(2,8)表征.网络中所有存在的e(i,j)组成链路集合E.在多跳分级的网络模型中,针对每个节点V(i)分别定义2个物理特征,即H(i)和Q(i).其中H(i)表示节点i所在的层数,Q(i)表示根据节点传输需求而定的节点在一个通信周期中周期性数据的通信量.无线网络的通信周期是指所有节点与网关进行一次通信所需要花费的时间.由于无线网络的通信过程是不断重复执行超帧的过程,本文用执行一个超帧所使用的时间来表示通信周期.

根据上述网络模型的定义,可以得到网络节点信息表.以图4中表示的网络为例,其节点信息表如表1所示.通过具体的网络信息表可知每个节点向网管传输的周期性数据量并不相同,即每个节点的传输能力存在差异.

表1　无线网络节点数据流量表

2链路选择与时隙分配的同步优化

2.1网络性能优化总体架构

本文仅考虑节点将数据传输至网关的过程,这个过程与数据从网关发向节点的过程刚好相反.为避免无效传输带来的系统损耗,规定在节点与网关相互通信的过程中,数据的传输遵从以下几个原则：1)数据只从距离网关远的节点向距离网关近的节点传输；2)节点通信只在邻居节点之间进行;3)根据数据聚合机制,节点接受到的数据可以和节点自身的数据聚合为一个数据包同时发送.

根据以上条件,可以得出整个无线网络所有存在的合理的链路：用e(i,j)表示数据由节点i传输到节点j的链路,节点i是链路的发送节点,节点j是链路的接收节点.这里不区分数据流的方向,即e(i,j)=e(j,i).链路e(i,j)存在的条件是满足:

(1)

搜索整个无线网络的所有链路后,选取以节点i作为发送节点的所有链路构成集合L(i).L(i)包含了所有以节点i为发送节点的链路.所有同时满足H(i)-H(j)=1,Aij=1条件的链路e(i,j)都属于L(i).节点i可以从集合L(i)中任意取出一个链路作为自己的发送数据链路.那么,

L(i)∩L(j)=φ,i≠j；

(2)

L(1)∪L(2)∪…L(N)=E,i≠j.

(3)

图5　链路选择和时隙分配同步优化流程图Fig.5　Flowchart of synchronous optimization of Link-scheduling and Timeslot-assignment

链路选择和时隙分配共同组成网络初始化中的资源分配方案.链路选择和时隙分配的任务是在保证网络所有节点数据正常传输的情况下,尽量使用少的链路和时隙,以达到提高无线网络性能的目的.两者相互制约,共同影响着网络的性能.链路选择和时隙分配同步优化流程如图5所示.先确定整个网络的链路情况,并根据需要选择合适的链路和适当的时隙分配方案,在保证网络数据传输无故障的前提下提升网络性能.

在链路选择问题中,为了避免在网络传输过程中产生冲突,采用链路染色算法把有冲突的链路区分隔开.链路之间存在冲突是指两链路同时传输数据时会产生故障,导致数据无法正常传输.e(i,j)∩e(i′,j′)≠φ,表示两链路之间存在冲突,不可以同时传输数据.链路染色算法用尽量少的颜色把有冲突的链路染上不同的颜色,再给不同颜色的链路分配不同的时隙用于数据传输,从而完全避免数据在网络中传输的冲突问题.链路染色算法的执行顺序如下：

1)初始化染色板,把颜色按顺序排列,本文使用序号代表颜色分类,每一个颜色序号代表不同颜色,并不使用真实的颜色，如：绿色、红色等；

2)由最内层的第一条链路开始染色,给第一条链路赋予第一种颜色；

3)按照链路的顺序给链路分配颜色,每一条链路都从第一种颜色开始分配,检查是否有冲突,有冲突时换下一种颜色,直到冲突消失；

4)整个网络染色完毕后,统计使用了多少种颜色(颜色的总数目用s表示)以及每条链路使用颜色的情况.

2.2网络性能优化指标

通过适当的链路选择和时隙分配可以给无线网络的性能带来很大的提升,这里把链路选择和时隙分配统称为链路调度问题.网络的链路调度属于多目标优化范畴,常见目标主要包括节点终端的采样率、无线节点能耗、端到端的延迟和网络节点的均载.

1)节点终端的采样率.单位时间内采集的数据量和时隙总数目有关,WIA-PA超帧中时隙总数目越小,网络链路的利用率越大,终端采样率越高.

2)无线节点能耗.因为无线传感器设备需要自身供电,而一般电池电量都有限,且更换电池对工厂来说又非常耗时耗资,所以如何降低无线节点的能量消耗也是时隙分配中的一个亟须优化的任务.

3)端到端的延迟.端对端的延迟定义为从发送节点产生信号到接收节点完整地接收信号所耗费的时间,表征网络实时性的强度.在TDMA模型中时间被划分为多个等长的时隙,端到端的延迟表示节点数据传输耗费时隙的个数.

4)网络节点的均载.如果多个节点数据传向同一个节点,容易导致该节点超载,缓冲区溢出,信息传输出现故障.均衡网络节点负载也是很重要的一个研究方向.

由于WIA-PA无线网络中传感器、执行器等现场无线设备不参与网络的路由功能,耗能大大减小,这里只以如前所述的1)、3)、4)为网络的优化目标,提出以下3个网络性能评价指标.

1)终端采样率评价指标是时隙的总个数的倒数,这里时隙的总个数是指已选择的链路中存在的颜色的总数目nsum,样率评价函数如下：

F1=1/nsum.

(4)

(5)

式中：n1为一跳级别节点的数量,Q(i)为节点i的周期数据量.可以根据已经选择的链路得到一个网络的传输矩阵T,表示节点数据的传输过程.设无线网络共有N个节点,其中最大跳数级别为M,则T为M×N维.矩阵的第j列表示节点j数据的传输路径,第i行表示经过i跳后各节点数据到达的位置.Tij表示节点j数据经过i跳后到达的节点,若是节点数据没有经过M跳就已经到达网关节点1,那么同一列后面的元素全部赋值为0.

第14列的元素给出了节点14数据传输的路径图,节点14→8→2→1.对于任意Tij=x的所有节点j的数据在传输过程中都经过节点x,成为节点x负载的一部分.为此,定义节点自身数据流量加上所有经过节点x的数据流量Wx为节点x的负载：

∀Tij=i,Wi=∑Q(j).

(6)

第一层节点负载的平衡情况可以表示为

由于优化的目标函数值应为正值,且S随着系统性能的提升而增大,S的最大值与一跳级别的节点个数n1有关：

采用最大值减去平衡指标作为负载均差指标函数：

(7)

3)由于网络的延迟计算涉及到全部节点发送数据的延迟,采用网络平均延迟作为评价指标.由于无线网络采用TDMA信道接入机制,网络的通信周期被划分为一个个等长的时隙.假设一个时隙足够节点传输节点内的所有数据,那么节点的端到端延迟只与节点传输数据花费的时隙个数和等待过程消耗的时隙个数有关.每个节点传输数据花费的时隙个数只与其距离网关的跳数有关,距离网关的跳数即数据传输花费的时隙个数.等待过程的时隙个数则与链路时隙的顺序有关，是此数据从某一节点到达另外一个节点的延迟.D都是由两部分组成：

D=Dt+Dw.

式中：Dt、Dw分别为数据传输过程和等待过程花费的时隙个数.对于每一个节点,Dt是固定的,节点距离网关的跳数即是节点数据传输需要消耗的时隙.Dw与时隙的顺序密切相关.下一跳节点的时隙靠后,那么数据包可以聚合一起发送；如果下一跳节点时隙在前一跳节点之前,数据则会在节点缓冲区保存,直到下一个通信周期再进行传送.D(i)表示节点i的数据到达网关的总共延迟时间,那么整个网络的总延迟可以表示为

平均延迟Da=Dsum/N.为此,采用平均延迟的倒数作为网络延迟评价指标：

(8)

针对上述3个目标的网络优化问题,采用加权求和的方式,作为最终的优化性能指标：

F=αF1+βF2+γF3.

(9)

式中：α、β、γ分别为3个子性能指标的权重,满足α+β+γ=1.

2.3网络优化算法具体实现

采用遗传算法实现具体的网络链路和时隙分配同步优化.遗传算法是一种模拟自然界遗传机制的过程最优解搜索算法,不需要描述问题的全部特性,直接处理的对象是优化参数集而不是问题本身,非常适合多目标寻优的无线网络链路选择和时隙分配问题.

2.3.1编码设计由于遗传算法处理的对象是问题的参数集,合理的编码会很大程度提升算法的运行效率.本文中要处理的链路选择问题和时隙分配问题都属于无线网络初始化的资源分配问题,需要同步优化以实现网络的性能提升.为解决链路调度的同步优化问题,需要遗传算法采用分开编码、同步优化的方式工作，通过不同的编码方式将链路选择和时隙分配问题映射到不同的数域.

1)链路选择编码方案.

链路选择的目的是保证网络中所有节点都能够与网关通信,这是所有数据正常传输的前提.这里仅研究节点将数据传向网关的过程,除网关以外的所有节点都拥有至少一条以自身为发送节点的链路,即可保证全网数据都可以正常传输.节点i的所有传输链路构成集合L(i),从节点1到节点N,这种结合共有N个,分别是L(1),L(2),…,L(N).为保证网络数据的正常传输,须在每个集合中取出至少一条链路构成整个网络的传输链路.为了计算方便,在每个集合中仅取出一条链路构建网络传输链路,则网络传输最终由N条链路组成,与节点数目相同.

设定无线网络共有N个无线节点,定义集合{L(1), L(2),…,L(N)}中拥有的最大元素个数为Lmax.根据上述条件,定义一个如图6(a)所示的N× Lmax的矩阵,用来描述N个节点的可选择链路集,实际上是将集合{L(1), L(2),…,L(N)}纵向排列成矩阵形式.图6(a)中第i行的元素表示节点i向网关传输数据时可以选择的链路,“*”表示此传输链路不存在.网关节点不可作为发送节点,因此矩阵的第一行全为“*”,第2个节点作为发送节点的链路只有一个e(2,1),其他位置全部用“*”填充.

图6　节点可选链路集和链路选择编码Fig.6　Selectable link set of nodes and Link-schedulingencoding

依照图6(a)中的矩阵,对链路选择问题进行N×Lmax矩阵编码,如图6(b)所示.编码规则如下：使用三标量编码的方式,对于图6(a)中所有值为“*”的位置全部赋值“*”,表示不可操作的位置；在剩余位置中的每一行中随机选出一个位置赋值为1,表示选取该位置的链路作为节点的发送链路,剩余位置赋值为0,表示虽然该位置有链路存在但是没有被选中.值为0或者1的位置都是遗传算法可以操作的位置,交叉变异等操作均在可操作的位置上进行.将图6(a)作为6(b)的参照系使用,两者结合可以得出网络传输所使用的链路.

2)时隙分配编码方案.

时隙分配的编码方案相对简单,采用十进制编码.根据已经得到的网络染色时使用的颜色总数NSUMC,采用随机分配编码,如图7所示.图中,1～NSUMC表示第一种颜色到第NSUMC种颜色,空格内的元素表示该颜色分配到的时隙.编码时保证1～NSUMC每种颜色都被分配时隙.

图7　时隙分配编码Fig.7　Timeslot-assignment encoding

链路编码和时隙编码分别是为了解决链路选择和时隙分配的问题,但是在优化无线网络时必须将两者结合使用才能得出网络的数据传输链路以及链路时隙的分配方案.根据得到的传输链路和该链路分配到的时隙,就可以对网络进行性能评估.

图8　同步优化算法流程图Fig.8　Flow chart of synchronous optimization

2.3.2优化算法流程网络链路和时隙分配同步优化算法流程如图8所示.进行算法初始化,确定遗传优化中使用的参数,如：初始种群数量、交叉率、变异率以及最大迭代次数等.随机生成初始种群时,每个种群中的个体都同时拥有2个独立的染色体：链路选择染色体、时隙分配染色体,分别使用图6(b)和图7中的编码方式进行编码.链路选择染色体给出网络的传输链路,时隙分配给出网络为链路分配的时隙,在计算个体适应值时需要使用到2个染色体.在个体中进行具体的交叉操作和变异操作时,2个染色体也使用不同的方式进行；在个体的一次交叉或变异过程中,2个染色体是分开进行的.在进行一次交叉变异后会得到新的初始种群,检测新种群是否到达要求的性能指标,如若没有达到,继续循环运行程序,若是新种群达到要求性能指标或是算法循环次数达到上限次数,技术算法得到最终的种群.

在计算完种群的个体适应值之后,选取适应值高的一部分进行交叉操作.交叉操作是遗传算法的核心+部分,是种群多样性的保证,交叉操作决定了遗传算法的全局搜索能力.本文研究因为每个个体中有2种不同的染色体(与不同的编码方式相对应),所以会有2种交叉方式.链路选择染色体在进行交叉时采用单行交叉模式,随机选择染色体某一行作为交叉对象,将染色体选中的2行进行数据交换.时隙分配染色体在进行交叉时采用互换染色体策略,直接互换2个个体中的时隙分配染色体.

在产生的新个体中进行变异操作时，同样也采用2种不同的策略.在链路染色体中随机选择一行进行变异,即在可操作的位置中随机选择一个0位置和1位置交换.时隙染色体采用双点变异,随机选择2个点互换位置.

3仿真研究

本文的仿真对象采用3层14个节点的无线网络,如图4所示.采用全局干扰、跳数级别相差1的节点互为邻居节点的模式,节点的分布以及每个节点周期内发送的数据量如表1所示.

节点的数据量Q以最小的数据包为单位.初始种群的数量Nc=60，交叉率Pc=80,变异率Pm采用随迭代变化的自适应变化率：

(10)

式中：Fmax(t)为第t代种群中最优个体的适应值,Fa(t)为第t代种群的平均适应值.这里采用最大迭代次数λ=100作为优化结束标准.性能指标加权因子分别取α=0.3、β=0.4、γ=0.3.

针对交叉和变异操作后产生的新个体,采用无差选取方式产生新的种群,即将父代和子代所有个体一起比较适应值,选择适应值较大的前Nc组作为新一代的种群,迭代100次直至算法结束.

图9　仿真实验中无线网络传输性能趋势图Fig.9　Performance trend of wireless network transmission in simulation experiment

算法稳定收敛后,取稳定种群中优化后的分配方案,得到结果如表2所示.

参数设置完成后,重复运行50次遗传算法,可以得出种群的适应值变化图和目标函数随着迭代次数增加的变化趋势图，如图9所示.图中,F、σ分别为50次实验中种群的平均适应值、种群节点的负载标准差.可以看出,所有的种群适应值在初始阶段快速上升,随后追歼变缓到最后稳定收敛,但是不同组之间的初始值、稳定值和稳定速度之间存在差异.从图9(b)可以得到网络时隙总数nsum随着优化迭代次数的变化情况,所有实验中网络时隙总数随着迭代次数的增加呈下降趋势,某一些点可能会有小幅度的涨幅.这是由于在多目标优化问题中，某些时刻多个目标利益之间是相互冲突的,为了整体的优化目标往往会牺牲其中一个或几个目标的利益,以小的代价换取总体目标性能的大幅度提升.图9(c)、(d)与图9(b)相似,总体的趋势是无线网络的传输性能不断提升直至最终趋于稳定,但是提升的过程中偶尔会有一些小的波动.

50次实验随机生成的初始种群不同,得到的最终收敛种群也不同,如表3所示为种群适应值、网络时隙总数、网络节点负载均差和网络的平均延迟在50次实验中的统计情况.如图10所示分别为相应的对比图.图中,实线是初始种群指标的曲线,虚线是优化后的种群的指标曲线.从表3和图10可以看出,经过优化后网络的3个性能指标均有不同程度的提升,对网络进行优化可以明显改善网络的性能.由于是多目标的优化,没有一个固定的最优解,最优解并不完全固定.

表2　优化后种群的分配方案

为验证本文算法的有效性,选择文献[5]中的图染色无线MAC改进的链路调度算法(modifiedlinkschedulingalgorithm,MLSA)作为比较.选取时隙总数、节点负载和节点的平均延迟作为比较对象,以节点的数量作为自变量.选取节点数目为50、100、150、200、250,分析、比较2个算法的性能.因为本文算法在选择传输链路时仅考虑相邻层上节点之间的连接,不考虑同层和跨多层节点的连接,所以会大大减小链路染色中链路的数量,减小网络所使用的时隙个数.

表3优化前后种群各项评价指标对比

Tab.3performanceindexofno-optimizedandoptimizedpopulation

评价指标种群最大值最小值平均值方差适应值初始种群0.26180.24680.25698.1650×10-4优化种群0.38040.34800.36800.0043时隙总数初始种群10.791210.343810.55460.3540优化种群7.00005.00005.537422.1710节点均差初始种群0.17240.12290.14880.0051优化种群0.00832.6670×10-40.00242.3098×10-4平均延迟初始种群14.192913.530114.09612.5925优化种群7.76925.38466.378616.1445

图10　初始化种群与优化后种群的性能对比图Fig.10　Performance comparison of normal population and optimized population

如图11所示为分别采用本文算法与文献[16]的算法得出的结果.可以看出,使用本文算法可以有效减小网络时隙总数和数据的传输延迟,增加网络采样率.基于链路-时隙编码的GA算法可以得到更好的网络性能,特别是当节点数目较多时,简化的网络模型为算法带来更加快速有效的运算效率.MLSA算法中与网关直接通信的节点只有一个,网络中所有数据都需要经过这个节点传输,无法均衡该节点的负载.由此可知,运用本文算法可以将网络中的所有数据平分到第一层的所有节点中,相比MLSA算法,本文算法大大减轻了节点的负载.基于链路-时隙双层编码的GA算法不仅能获得较好的采样率和实时性能,并且能够兼顾到节点的负载.

本文所提的算法在运行过程中也存在不足之处.当网络节点过多时,算法运算时间需要几十分钟或更多,这影响了算法的计算效率.

图11　时隙总数与平均延迟的传输性能对比图Fig.11　Transmission performance of double layer encoding GA and MLSA

4结语

本文在无线网络传输特性的基础上,提出一种多跳分级的网络模型,将分布的网络节点层次化,将无线网络物理上的距离限制表示为网络在逻辑上跳数结构限制.在此模型的基础上,通过将图染色算法与双层编码的遗传算法相结合,保证网络在无冲突的情况下优化网络性能指标,通过链路选择和时隙分配双层编码的方式解决整个网络链路选择和时隙分配的同步优化问题.仿真结果表明：通过优化,网络的整体性能得到了较大的提升,完成了整个网络的布局和资源分配,较好地解决了链路选择和时隙分配相互干扰的问题；不足之处是当面对复杂的大型网络时该算法的计算效率低下.面对多节点的大型网络,如何进一步提升优化速率有待进一步研究.

参考文献(References)：

[1]ERGENSC,VARAIYAP.TDMAschedulingalgorithmsforsensornetworks[J].WirelessNetworks, 2010,16(4): 985-997.

[2]GANDHAMS,DAWANDEM,PRAKASHR.Linkschedulinginsensornetworks:distributededgecoloringrevisited[C] ∥Proceedingsofthe24thAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties(INFOCOM′05).NewYork:IEEE, 2005: 2492-2501.

[3]ZHANGX,HONGJ,ZHANGL,etal.CC-TDMA:coloring-andcoding-basedmulti-channelTDMAschedulingforwirelessadhocnetworks[C] ∥WirelessCommunicationsandNetworkingConference.HongKong:WCNC, 2007: 133-137.

[4]TSVETKOVT,SANNECKH,CARLEG.Agraphcoloringapproachforschedulingundoactionsinself-organizingnetworks[C] ∥ 2015IFIP/IEEEInternationalSymposiumonIntegratedNetworkManagement(IM).Ottawa:IEEE, 2015: 348-356.

[5] 赵亚楠. 无线传感器网络中的时分复用调度算法研究[D].吉林：吉林大学,2013.

ZHAOYa-nan,Researchontimedivisionmultiplexingschedulingalgorithminwirelesssensornetworks[D].Jilin:JilinUniversity, 2013.

[6]SRIDHARANA,KRISHNAMACHARIB.Max-minfaircollision-freeschedulingforwirelesssensornetworks[C] ∥ 2004IEEEInternationalConferenceonPerformance,Computing,andCommunications.Phoenix:IEEE, 2004: 585-590.

[7]GANDHAMS,ZHANGY,HUANGQ.Distributedminimaltimeconvergecastschedulinginwirelesssensornetworks[C] ∥ 26thIEEEInternationalConferenceonDistributedComputingSystems, 2006.ICDCS2006.Lisbon:IEEE, 2006: 50-50.

[8]DJUKICP,VALAEES.Linkschedulingforminimumdelayinspatialre-useTDMA[C] ∥INFOCOM2007. 26thIEEEInternationalConferenceonComputerCommunications.Anchorage:IEEE, 2007: 28-36.

[9]KALASM,MUSHAMR,REDDYMPK,etal.Radioco-locationawaregenericmulti-radiomulti-channelconflictgraphgeneration[J].arXivpreprintarXiv: 1412.2566, 2014.

[10]ABBASSH,HONGSH.AschedulingandsynchronizationtechniqueforRAPIEnetswitchesusingedge-coloringofconflictmultigraphs[J].JournalofCommunicationsandNetworks, 2013, 15(3): 321-328.

[11]GOBRIELS,MOSSED,CLERICR.TDMA-ASAP:SensornetworkTDMAschedulingwithadaptiveslot-stealingandparallelism[C] ∥ICDCS′09.29thIEEEInternationalConferenceonDistributedComputingSystems.Montreal:IEEE, 2009: 458-465.

[12]LUOXY,YANYL,LISB,etal.Topologycontrolbasedonoptimallyrigidgraphinwirelesssensornetworks[J].ComputerNetworks, 2013, 57(4): 1037-1047.

[13]MAJ,LOUW,LIXY.Contiguouslinkschedulingfordataaggregationinwirelesssensornetworks[J].IEEETransactionsonParallelandDistributedSystems, 2014, 25(7): 1691-1701.

[14]ZHOUY,LIXY,LIUM,etal.Throughputoptimizinglocalizedlinkschedulingformultihopwirelessnetworksunderphysicalinterferencemodel[J].IEEETransactionsonParallelandDistributedSystems, 2014, 25(10): 2708-2720.

[15]KARK,SARKARS,GHAVAMIA,etal.Delayguaranteesforthroughput-optimalwirelesslinkscheduling[J].TransactionsonAutomaticControl,IEEE, 2012, 57(11): 2906-2911.

[16]KHANMF,FELEMBANEA,QAISARS,etal.Performanceanalysisonpacketdeliveryratioandend-to-enddelayofdifferentnetworktopologiesinwirelesssensornetworks(WSNs) [C] ∥ 2013IEEENinthInternationalConferenceonMobileAd-hocandSensorNetworks(MSN).Dalian:IEEE, 2013: 324-329.

[17] 张晓轲,曾健平,徐朝农,等.基于分布式图染色的无线MAC调度算法研究[J].计算机研究与发展,2011(增2)：216-222.

ZHANGXiao-ke,ZENGJian-ping,XUChao-nong,etal.ResearchonwirelessMACschedulingalgorithmbasedondistributedgraphcoloring[J].ComputerResearchandDevelopment, 2011(Suppl.2)： 216-222.

[18]ZENGJP,ZHANGXK,XUCN,etal.MACschedulingalgorithmforwirelessnetworksbasedondistributedgraphalgorithm[J].ComputerEngineering, 2012, 19: 4.

收稿日期：2014-12-04.

基金项目：国家自然科学基金资助项目(61573050); 北京市自然科学基金资助项目(4132044).

作者简介：司恩波(1992—),男,硕士生,从事工业控制系统安全性研究.ORCID：0000-0001-9513-405X. E-mail: sienbo1992@163.com 通信联系人：王晶,女,教授,ORCID：0000-0002-6847-8452. E-mail: jwang@mail.buct.edu.cn

DOI:10.3785/j.issn.1008-973X.2016.06.027

中图分类号：TN 92

文献标志码：A

文章编号：1008-973X(2016)06-1203-11

Synchronousoptimizationoflink-schedulingandtimeslot-assignmentforindustrialwirelessnetwork

SIEn-bo,WANGJing,JINQi-bing,ZHOUJing-lin

(School of College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029,China)

Abstract:The transmission performance of wireless network was improved through static optimization with the combination of Link-scheduling and Timeslot-assignment algorithms, focusing on the industrial wireless network. Link-scheduling algorithm allocated the spatial resource and Timeslot-assignment algorithm distributed the temporal resource, the interaction of which impacts the transmission performance of wireless network commonly. Firstly, a multi-hops grading model was proposed according to the transmission performance of wireless network to build a hierarchical wireless network, through which the connections between wireless nodes were simplified. Then a scheme for synchronous optimization of Link-scheduling and Timeslot-assignment was given based on the proposed model. Secondly, for the two different problems that belonged to space and time, respectively, link coloring algorithm was used to separate conflicting links for the sake of avoiding conflict data transfer in wireless network. Hierarchical coding scheme was proposed and a genetic algorithm (GA) with double-layer encoding was put forward to connect Link-scheduling and Timeslot-assignment algorithms by using implicit parallelism and combinatorial optimization, which could eliminate the interference between them. At last, a synchronous optimization strategy based on genetic algorithm was formulated and verified. Results show that the transmission performance of network sampling rate, the network delay and the network nodes load get further improvement by using optimized algorithms with synchronous strategy.

Key words:WIA-PA wireless network; multi-hops grading model; synchronous optimization; geneic algorithm; double-layer encoding; Link-scheduling; Time slot-assignment