张本宏,　邱　睿,　黄琳琳

(1.合肥工业大学 计算机与信息学院,安徽 合肥　230009; 2.合肥工业大学 安全关键工业测控技术教育部工程研究中心,安徽 合肥　230009)



一种用于工业无线传感器网络的动态调度方法

张本宏1,2,邱睿1,黄琳琳1

(1.合肥工业大学 计算机与信息学院,安徽 合肥230009; 2.合肥工业大学 安全关键工业测控技术教育部工程研究中心,安徽 合肥230009)

摘要:传输调度是提高无线网络通信性能的重要手段，针对工业无线传感器网络,文章提出一种基于距离矩阵的动态调度方法。根据网络的拓扑结构建立初始时隙分配计划以及距离矩阵,构建时隙分配表并确定节点的发送和接收时隙。该方法既考虑了网络拓扑结构的影响,又考虑了节点数据产生周期的影响。仿真结果表明,该方法能显著降低网络的平均发送时间,提高数据传输的保真度。

关键词:工业无线传感器网络;确定性;调度方法;时隙分配;距离矩阵

无线网络因其布线简单、安装维护方便,逐渐在工业现场得到应用[1-3]。与无线传感器网络相比,应用于工业现场的工业无线传感器网络(Industrial Wireless Sensor Networks，IWSNs)对数据通信的确定性和可靠性要求更高[4],因此,对IWSNs的通信进行合理调度,确保数据传输过程中的确定性和可靠性,显得尤为重要。

无线通信的调度方法按照介质访问控制方式主要分为基于竞争、基于固定时隙分配和两者相结合3种[4-5]。由于基于竞争的方法,可能在多个节点同时发送数据时产生碰撞,难以保证时延的确定性,因此在工业现场,通常采用基于固定时隙分配的方法[5]。目前,众多研究者针对不同的应用和不同的优化目标,对基于固定时隙分配的调度方法进行了研究。文献[6-7]针对多跳多基站无线网络环境,设计了一种基于干扰管理的高容量跨层优化策略,通过迭代方式反复求取更优的链路分配和路由,但以最大化整个网络的吞吐量为目标;文献[8]针对无线传感器/执行器网络,基于混合模拟退火的微粒群算法,提出了一种动态调度方法,但主要考虑的是能量均衡因素;文献[9-10]针对周期性的查询应用,设计了一种查询调度方法RTQS(real-time query scheduling),但未考虑节点数据产生周期不同的影响;文献[4,11]对符合WIA-PA标准的工业无线网络的调度方法和路由选择进行研究,但未给出各个节点发送时隙的分配机理。

本文在上述文献的基础上,针对IWSNs的应用,提出一种基于距离矩阵的动态调度方法,在为节点进行时隙分配时,既考虑了网络拓扑结构的影响,又考虑了节点数据产生周期的不同,可满足IWSNs对数据传输过程中数据可靠性和时延确定性的要求。

1问题描述

IWSNs由工作节点、路由节点、汇聚节点和管理节点组成。工作节点周期性产生数据,路由节点既可以周期性产生数据,又具有路由和信息转发功能。图1所示为一种示例IWSNs的拓扑结构,其中a为汇聚节点,叶子节点为工作节点,其他节点为路由节点。与传统的无线传感器网络相比,工作节点或路由节点在数据产生以后,必须在一定时间内发送到汇聚节点。

图1　网络拓扑图

本文对IWSNs调度方法的研究,主要基于以下假设:

(1) 节点间任何数据的一次发送,均在一个时隙内发送完毕。

(2) 所有数据的产生均具有周期性。

(3) 所有节点对网络的全局信息包括节点位置、数据产生周期均已知。

2基于距离矩阵的动态调度方法

基于固定时隙分配的调度方法,本质上是为每个节点合理安排发送时隙,由于时隙调度是NP难问题,通常采用启发式搜索方法[12]。本文的调度方法也采用启发式搜索方法,其步骤如下:

(1) 根据网络的拓扑结构和冲突情况,建立时隙初始分配计划。

(2) 为每个数据发送产生计划实例,建立距离矩阵。

(3) 建立节点时隙分配表,确定发送和接收时隙。

2.1建立初始时隙分配计划

初始时隙分配计划是根据网络拓扑产生的有序时隙序列,每个时隙中包含了若干互不冲突的传输链路集合,将初始时隙分配计划记为S={s1,s2,…,sL},si表示计划中的不同时隙,L为初始时隙分配计划的长度。

在构造初始时隙分配计划时,将IWSNs视为层次结构,维护completed与eligible 2个集合,completed集合包含已分配了时隙的节点,eligible集合包含了completed集合目前可达的待分配节点,但eligible集合中的节点本身不属于completed集合。不断选择eligible集合中优先级最高的节点,为其分配时隙,将节点移动到completed集合,再将此节点的孩子节点加入eligible集合。

表1　示例网络的初始时隙分配计划

2.2建立距离矩阵

初始时隙分配计划建立后,如果每个节点按照计划中的时隙循环发送数据,在数据发送时不产生冲突,但显然该发送方式并发效率较低。例如在时隙1,只有节点o发送数据,而实际上此时节点x、w等均可同时发送。为了提高发送效率,需进一步提高数据发送的并发性。为此,引入定义1～定义4:

定义1初始时隙分配计划的每次执行称为计划实例。

初始时隙分配计划的每次执行并不一定从时隙1开始,1个计划实例可能包括1个或多个数据的一次完整发送。例如,对于图1的示例网络,如果在某个时隙,只有节点y有数据发送,则产生新实例时,该实例从时隙3开始,也即该实例只包括从时隙3到时隙7的5个时隙。

对于不同的实例,如果在发送时间上存在重叠,就可以提高发送效率。因此最大限度地提高时隙的重叠数,即减小新实例和正在执行实例的相隔时间是提高发送效率的关键。由于不同实例的时隙间可能存在冲突,不能随意地选择新实例开始时间,而必须满足一定条件。

定义2如果计划实例的si与sj中所有的链路都是无冲突的,则称时隙i与时隙j可以并发执行。

定义3如果新实例与当前实例未执行的部分重叠的时隙都是可以并发执行的,则称这2个实例能够并发执行。

定义4新实例与当前实例未执行的部分能够并发执行的最小时隙间隔,称为实例距离。

距离矩阵就是用来表示实例距离的矩阵。对于长度为L的初始时隙分配计划,当2个实例间的开始时间间隔大于L时不会产生冲突。因此对于长度为L的初始时隙分配计划,最多有L个时隙实例冲突,因此其距离矩阵可用L×L的三角矩阵D表示,元素Di,j表示当前计划实例运行到时隙i时,从j时隙开始的新实例应延迟执行的时隙数。

对于对角线以下区域各值,求解步骤如下:

(1) 假设新实例可与当前实例同时开始。

(2) 检查新实例与当前实例能否并发执行,如果可以并发执行,则当前的延迟执行时隙数即为所求；否则,将新实例延迟一个时隙,再次执行步骤(2)。

由于从较晚相对时隙开始的新实例能够合并到从较早相对时隙开始的已有实例中,在距离矩阵中对角线及对角线以上区域均为0。

由图1示例网络计算得出的距离矩阵为:

2.3确定发送和接收时隙

网络中各个节点根据初始时隙分配计划与距离矩阵,动态产生时隙分配表,用于决定节点的数据发送和接收时隙。

时隙分配表在逻辑上是一种循环队列,每个节点均存在一张时隙分配表。队列的每个元素表示在一个相对时隙内节点处于的状态,0表示发送状态,1表示接收状态,其他值表示空闲状态,每个节点使用一个时隙指针指示当前所处的时隙。

为了产生时隙分配表,节点维护一个就绪计划实例队列ready,用于存储所有已经安排好发送时隙的计划实例。节点在每个时隙到来之前,尝试将在此时隙开始的数据发送任务加入已有实例中。如果实例队列中存在这样一个实例,其当前所处的时隙早于或等于数据的源节点在初始时隙分配计划中的时隙,则该数据能够加入这个实例。如果有多个这样的实例,选择最早开始的一个。如果不存在这样的实例,则创建一个新实例,再将数据发送任务加入此实例。

对于一个新实例,需要确定它的发送时间,以便更新时隙分配表。发送时间可根据距离矩阵计算确定,分配流程如图2所示,其中s表示新实例的开始时隙数,i表示就绪计划实例队列中的实例,curSlot(i)表示实例i的当前相对时隙。

考虑到距离矩阵反映的是单个当前实例与新实例的计划距离,而非所有当前实例与新实例的计划距离,将具体求解步骤表述如下:

(1) 假设新实例的开始时隙数等于当前时隙数。

(2) 计算就绪计划实例队列中,每一个当前实例未执行的部分与新实例的计划距离,并选出其中的最大值dmax。

(3) 如果dmax≠0,将新实例的开始延迟dmax个时隙,转到步骤(2)；否则新实例可以与所有当前实例并发执行,求解结束。

图2　时隙分配流程图

数据加入实例后,即表示数据的发送时隙已被确定,数据传输到汇聚需经过的每个节点修改各自的时隙分配表,在数据对应的实际工作时隙进行发送或接收。时隙分配表总是丢弃已经逝去的时隙项,而一个新实例的开始时间间隔不会大于L,也即时隙分配表的长度不会超过2L。

3算法仿真

为了验证本算法的性能,在网络仿真器NS3上进行仿真,并与文献[10]的RTQS方法进行性能比较。在仿真场景中,网络带宽为2 Mb/s,网络中数据的长度被设置为固定的200 Bytes(包含帧头),时间片长度为10 ms。

3.1不同网络规模下的性能比较

在本次比较中,网络中的数据数量与节点数呈正相关,数据的产生周期与截止期相同,并被随机划分为3种长度,比值为1∶1.2∶1.4,基准长度与初始时隙分配计划长度相等。

在不同的网络规模中本文方法与RTQS的响应时间以及保真度情况如图3所示。在本文中,响应时间指数据从产生到被基站接收所流逝的时间,而数据保真度是指数据能够在截止期前送到基站的比例。

由于RTQS中并未考虑到数据发送任务于不同周期产生的情况,将RTQS的查询频率控制在不同的值上进行了2次仿真,2种频率分别是网络中周期最快任务的产生频率以及最慢任务的产生频率。

在图3中可以看出,高频率RTQS的响应时间低于低频率RTQS的响应时间,而数据保真度则相反,高频率RTQS的数据保真度更高。

本文算法与2种情况的RTQS相比,平均响应时间更低,而数据保真度更高。在网络规模较小时,由于调度计划长度小,两者响应时间差异不大,但是当网络规模逐步变大时,由于调度计划长度随之增大,而RTQS没有考虑到任务产生周期的不同,只能在统一的时间发出一次完全的查询,造成周期与查询间隔不一致的任务响应时间恶化,进一步导致了数据保真度的降低。

图3　不同网络规模下的性能比较

3.2不同查询频率下的性能比较

在本次比较中,网络中节点数量被固定为40个,每次仿真中网络拓扑是一致的,数据发送任务仍然被划分为3种,通过改变任务的基准周期长度来改变网络的查询频率。不同查询频率下本文方法与RTQS的响应时间以及保真度情况如图4所示。

在查询频率较低时,本文算法响应时间低于RTQS,且数据保真度更好,随着查询频率升高,本文算法由于新实例产生过于频繁,越来越多的实例从初始时隙分配计划的第1步开始,因此2种方法表现接近一致。

图4　不同查询频率下的性能比较

4结束语

本文研究了在工业无线传感器网络中基于距离矩阵的动态调度方法。根据工业无线传感器网络的特点,设计了初始时隙分配计划与距离矩阵,以此为依据进行动态调度。通过仿真证明了本文提出的调度方法可以在保证网络可靠性的前提下,合理分配时隙,降低网络的平均响应时间,并提高数据保真度。

[参考文献]

[1]Gungor V C，Hancke G P.Industrial wireless sensor networks:challenges，design principles，and technical approaches[J].IEEE Transactions on Industrial Electronics,2009，56(10):4258-4265.

[2]杨成,冯琳，魏振春,等.基于数据插值和权重指数的矿井机车无线定位方法[J].合肥工业大学学报:自然科学版，2013，36(11):1331-1334.

[3]Bal M.An industrial Wireless Sensor Networks framework for production monitoring[C]//2014 IEEE 23rd International Symposium on Industrial Electronics (ISIE).IEEE，2014:1442-1447.

[4]王平，刘其琛，王恒，等.一种适用于 ISA100.11a 工业无线网络的通信调度方法[J].仪器仪表学报，2011，32(5):1189-1195.

[5]张晓玲，梁炜，于海斌，等.无线传感器网络传输调度方法综述[J].通信学报,2012,33(5):143-157.

[6]石雷，韩江洪，石怡，等.多包接收无线 Mesh 网络的跨层优化[J].应用科学学报，2012，30(3):227-233.

[7]石雷，韩江洪，石怡，等.无线多跳网络下基于干扰管理的高容量跨层优化策略[J].通信学报，2014，35(12):89-97.

[8]易军，石为人，唐云建，等.无线传感器/执行器网络任务动态调度策略[J].电子学报，2010，38(6):1239-1244.

[9]Chipara O，Lu C，Stankovic J，et al.Dynamic conflict-free transmission scheduling for sensor network queries[J].IEEE Transactions on Mobile Computing，2011，10(5):734-748.

[10]Chipara O，Lu C，Roman G C.Real-time query scheduling for wireless sensor networks [J].IEEE Transactions on Computers，2013，62(9):1850-1865.

[11]王恒，李敏，刘其琛，等.一种基于确定性调度的工业无线网络路由算法[J].仪器仪表学报，2011，32(9):1921-1928.

[12]毛剑琳，吴智铭.无线传感器网络 TDMA 调度的能量-时延 Pareto 优化[J].控制与决策，2007，22(9):967-971.

(责任编辑马国锋)

A dynamic scheduling method for Industrial Wireless Sensor Networks

ZHANG Ben-hong1，2,QIU Rui1,HUANG Lin-lin1

(1.School of Computer and Information， Hefei University of Technology， Hefei 230009， China; 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education， Hefei University of Technology， Hefei 230009， China)

Abstract:Transmission scheduling is an important approach to improve wireless network performance. In this paper, a distance matrix based dynamic scheduling method for Industrial Wireless Sensor Networks(IWSNs) is presented. In the method, the initial slot allocation plan and the distance matrix are constructed according to the network topology， the slot allocation table is established，and then the transmitting and receiving slots of nodes are determined. The method not only takes into account the impact of network topology，but also considers the impact of data generation cycle of nodes. The simulation results show that the method can dramatically decrease the average response time of the network and improve data fidelity.

Key words:Industrial Wireless Sensor Networks(IWSNs); determinism; scheduling method; slot allocation; distance matrix

中图分类号:TP393.02

文献标识码：A

文章编号：1003-5060(2016)03-0333-05

doi:10.3969/j.issn.1003-5060.2016.03.009

作者简介：张本宏(1972-),男,安徽无为人,博士,合肥工业大学副教授,硕士生导师.

基金项目：国家自然科学基金资助项目(61370088);国家国际科技合作专项资助项目(2014DFB10060)和安徽省自然科学基金资助项目(1308085MF100)

收稿日期：2015-01-16；修回日期：2015-03-24