一种事件驱动的无线CPS实时消息并行调度方法

谭朋柳,冒苏敏,周 乐

(南昌航空大学 软件学院,南昌 330063)

0 概述

信息物理融合系统(Cyber-Physical System,CPS)[1-4]是一个前沿性研究领域,是信息系统和物理系统所有过程和功能的集合。CPS注重信息系统与物理系统的有机融合,将已有的各独立设备进行智能化连接,实现自适应的组网与交互,从而使系统之间实现相互感知与协同运作。同时,信息系统会收到物理系统的反馈,并根据反馈结果做出相应调整[5]。CPS技术在航空航天、电力、交通、医疗、环境监测、能源、农业等人类社会发展的各个领域都有着广泛的应用前景。CPS被普遍认为是计算机信息处理技术史上的下一次革命,Internet改变了人与人之间的交互方式,而CPS将会改变人与现实物理世界之间的交互方式[6]。

事件驱动的无线 CPS通常是由无线传感网络(Wireless Sensor Network,WSN)、数据与控制中心以及无线执行器网络(Wireless Actuator Network,WAN)等部分构成的大规模多跳无线自组织网络系统。其中,传感节点周期性地采集被控对象的信息,当感知异常时向中心实时返回异常事件消息,经控制中心处理后产生控制事件消息,并实时地传给 WAN相应的执行节点,执行具体控制任务,以便改变物理对象。如在一个医疗CPS系统中,医疗CPS是以保障生命安全为重要前提的网络化、智能化的医疗设备系统,通过各医疗单元之间的实时网络化通信和决策与控制,辅助医务人员实施操作,实现了医疗资源的高效合理利用[7]。

事件驱动的无线CPS是一种多跳无线自组织网络实时系统,实时性要求较高。为此,本文提出一种实时消息并行调度算法(RMPS),该算法主要研究并行消息的判定、消息传输的路径选择和消息的并行传输。

1 相关工作

近年来,国内外学者提出了许多无线传感器网络实时消息的调度方法,归纳起来主要分为基于竞争的方法、基于TDMA的方法、混合方法、基于优先级等。

1)在基于竞争的方法中,文献[8]在经典的HEED[9]协议基础上提出一种基于预约调度的无线传感器网络MAC协议(SSMAC)。该协议采用分布式竞争接入和预约发送,提高信道接入效率,支持服务质量(QoS)业务的传输,较好地解决了隐藏终端和暴露终端的问题。文献[10]提出一种按需汇聚的MAC协议,采用请求融合机制,将时隙分配给有数据需要传输的节点,大大节约了能量,降低了网络延时,但没有考虑事件优先级。文献[11]提出了L-CSMA协议。该协议为节点分配不同的优先级别,根据他们的位置在接近目的地时拥有更高的优先级调度权限。管理的首要任务是分配节点载波感知阶段的持续时间。文献[12]采用多个虚拟信道来避免拥塞问题,同时建立相应的链路调度表,减少信道间的碰撞问题,增加了网络吞吐量,但只针对低复杂网络。

2)在基于TDMA的方法中,文献[13]提出一种分布式数据融合调度算法,这种方式使用了一个多片结构调度节点到基站的数据传输,减少了数据的复杂程度和算法调度的运行时间。该算法不能随着网络的改变而自适应变化。文献[14]提出的算法在构建路由和传输调度阶段都进行优化,但它并不能有效降低消息传输端到端的延时。文献[15]提出了一种能量感知的消息调度方法(CC-TDMA)。虽然该算法降低了高优先级事件的传输延时,但它不是分布式的且不适合大型网络。文献[16]提出一种新的基于权重因子的消息调度算法,将信道质量、传输速度和事件优先级作为影响因子,提高了信道传输的公平性,但它不能保证消息的硬实时性。文献[17]针对实时性较高的无线网络,提出一种保障无线传感器网络消息实时性的调度方法(L-RQS)。该方法将消息进行优先级划分,同时根据路由节点转发的高优先级消息个数或等待时间设置节点的状态。该方法提高了网络吞吐量,但没有考虑消息传输的并行性。

3)在混合及优先级方法中,文献[18]将节点感知到的事件消息分为实时和非实时2种情况,实时消息进入优先发送队列,抢占现有时隙进行发送。这种方法可以提高实时消息的传输效率,但没有很好地解决消息间的干扰问题。文献[19]基于业务优先级对用户进行排队,可以有效地解决群组用户同时切换所可能造成的网络拥挤。文献[20]提出的算法将传感器节点划分为多个区域,每个区域内采用CDMA和TDMA混合调度,在数据传输之前不需要建立路由协议,减少了节点能量消耗和链路通信干扰,但该协议没有考虑事件的截止期限。

很多实时消息调度协议并不能满足事件驱动型无线CPS实时性的要求,也没有考虑消息传输中端到端的延迟和数据收集过程中能量的消耗等问题,而本文提出的RMPS算法通过建立实时消息并行优化模型,在此基础上采用图着色理论和禁忌搜索算法求解,实现了无干扰消息并行调度,提高了网络的信道利用率,降低了消息传输端到端的延时,减少了能量消耗。

2 系统模型

本文对网络模型做了如下简化假设:1)网络包含n个同构节点,均匀部署在M×M的正方形区域。2)网络各节点都有唯一的位置坐标,基站的位置坐标全网已知。3)网络在初始化时以分布式的方式存储,各节点知道自身的位置信息和其一跳范围内节点位置信息。4)网络中节点部署后静止,节点间的有效通信半径为Rc,干扰范围半径为Ri,且要求Rc

2.1 网络通信模型

通信模型描述了无线传感器网络的通信情况,本文采用网络拓扑图建立通信模型,模型中节点可以在各自的无线通信范围内相互通信。图1为一个网络拓扑图示例,其中,Node(a,b,…,p)代表节点,通信边表示两节点相邻且处在彼此的通信范围Rc内。通信边的子集可以构成一个用于数据聚合的路由树。

图1 网络拓扑示意图

2.2 网络干扰模型

在无线传感器网络中,消息间的干扰可以分为冲突干扰和并行干扰。因为一个节点不能同时拥有发送和接收2种状态,也不能同时接收2个发送节点的消息,如果违反了这2点,则称消息之间存在冲突干扰,如图2(a)、图2(b)所示。与已有的消息干扰模型不同,消息的并行干扰主要针对接收方起作用,如图2(c)所示判断消息m1(s1为发送方,r1为接收方)是否干扰消息m2(s2为发送方,r2为接收方),不需考虑s1与s2,r1与r2间的干扰情况,只判断r2是否在s1的干扰范围Ri之内来确定,如果在,则消息m1会干扰消息m2;否则不会。消息m2是否干扰消息m1也可以通过同样的方法确定。如果消息m1干扰m2,或者m2干扰m1,则称消息m1和m2之间存在干扰,存在干扰的2个消息只能串行发送;如果消息m1不会干扰m2,并且m2不会干扰m1,则称消息m1和m2之间互不干扰。

图2 消息干扰情况

2.3 消息并行调度模型

无线网络节点传输距离及干扰范围均有限,因此,互不干扰的消息可以并行调度。2个消息是否可以并行调度,主要看它们之间是否存在相互干扰,如果没有干扰,则可以并行调度,否则不能。因此,并行消息的判定问题可以转化为消息之间是否存在相互干扰的判定问题。通过网络干扰模型可以判定网络各消息间的干扰情况,互不干扰的2个消息可以并行调度。多个消息是否可以并行调度,主要看它们俩俩之间是否存在相互干扰。

本文采用消息图建立并行调度模型,图中顶点mn代表消息,实线代表干扰边,利用网络干扰模型判断消息间的干扰情况。假设网络中一组消息按截止期限从早到晚依次排列,为了让尽可能多的消息并行发送,提高信道利用率,缩短总延时,应建立实时消息调度并行优化模型。如果2个消息之间存在干扰,则在这2个消息对应的顶点之间画一条边。这样就得到如图3所示的消息图,没有干扰的消息可以并行发送。

图3 消息图

3 RMPS算法描述

RMPS算法在已知无线传感器节点的部署情况下,利用预约机制构建一个调度请求,用于各节点在上报阶段向基站发送时隙请求。基站将上报信息整合并构建并行调度表,让调度阶段内无干扰的消息尽可能同时传输。这种有序的时隙分配算法,既有效地避免了信道冲突,又实现了消息调度的并行优化,充分利用有限的时隙传输尽可能多的消息,最大化消息传输的并行程度。在并行调度表中无时隙分配的节点进入休眠状态,降低了节点的能耗。

算法按周期进行,每个周期可以划分为上报阶段、调度阶段和传输阶段。

1)上报阶段:用于事件消息的发现,采用固定顺序和固定长度分配方式,每个节点分配等同的时间片。节点检测到消息后,向基站发送少量的请求信息。

2)调度阶段:调度阶段也采用固定顺序和固定长度分配方式,每个节点分配相应的时间片。基站根据收到的请求信息构建消息并行调度表并下传调度表至各个节点。

3)传输阶段:该阶段细分为多个时隙,各节点根据按并行调度表中分配的时隙传输消息,未分配到时隙的节点则进入休眠状态。

算法帧结构如图4所示。

图4 RMPS算法调度周期划分

3.1 上报阶段

上报阶段运行了RTQS[21]算法中预约机制,预约机制类似于一种数据采集过程,即节点检测到环境中的消息后,并不立即发送,而是先发送一个预约请求,预约请求中只包含少量的信息CH(消息的编号mi,消息截止期限di,检测到消息的节点id)。考虑到基站必须收到所有的节点的上报信息,因此节点发送上报信息时具有先后顺序,父节点必须在收到所有子节点的上报信息后,将自身的信息和收到的信息进行数据融合,再将融合后得到的新上报信息发送给上一层的父节点,最终将所有节点的信息都上报给基站。

3.2 调度阶段

本文提出的算法用以解决无线CPS中调度阶段内消息的并行传输问题。在无线CPS中,节点具有周期性检测周围环境中特定数据的能力,当节点检测到的数据发生变化时,需及时将消息发送到基站。消息从源节点到目的节点往往要经过若干个中间节点。基站根据上报信息构建消息并行调度表,并行调度表包含消息传输的顺序步骤、节点在各时隙内所处的状态(发送状态、接收状态和休眠状态)和消息间并行调度情况。并行调度表的构建主要从路径选择和并行发送两方面来考虑。基站为每个消息的发送节点选择最优的接收节点,进而选择合适的传输路径,同时通过判断同一时隙内各个消息间的干扰情况,让无干扰的消息并行发送。

3.2.1 路径选择

网络中一组消息从源节点到目的节点往往要经过若干个中间节点,并且可能存在多条可达路径,因此,需要为链路中的每一跳传输选择合适的接收节点,进而选择合适的传输路径。无线CPS网络具有较高的服务质量(QoS)要求,消息的截止期限是网络需要考虑的首要因素。从发送节点(Si)相邻一跳范围内,选出能满足消息mi传输时限要求的节点作为Si的候选接收节点(CRi)。判断依据是在时隙tn内消息mi最晚发送时间L(i,tn)能否满足下列关系式:

t≤L(i,tn)=di-w(i,tn)

(1)

其中,t代表时隙tn段首对应网络全局时钟的时刻,di为消息mi的截止期限,w(i,tn)为消息mi经过CRi到达基站最短路径上所需的时间。

在选择消息传输链路时,还要考虑节点剩余能量和消息传输延时。在满足式(1)的候选接收节点CRi中,选出权值最高的节点作为最终的接收节点(Ri)。在时隙tn内,接收节点Ri的权值定义(RW)如下:

(2)

其中,Ec是表示候选节点CRi当前剩余能量,Em表示候选节点CRi的初始能量,NCRi表示候选接收节点CRi到基站最短路径上节点的数目,L(i,tn)表示消息i在时隙tn内最晚发送时间,α、β、θ是大于0的常数,且α+β+θ=1,它们是调节各因子在接收权值中的比重。针对本文所述网络,设定α、β、θ之间的关系为α<β<θ。

在式(2)中,引入了3个影响网络消息传输的因子:节点剩余能量,消息传输路径,消息传输延时。选择最短传输路径传固然可以最快传输消息,但最短传输路径上的某些节点可能成为“关键节点”,即其担任了较多链路的中继节点,能量消耗相对较大,为了平衡网络的能耗,提高消息传输成功率,需要考虑节点的剩余能量。同时,还考虑网络的平均延时,避免某些消息经过过多的节点传输。

以图1为例,网络中一组节点{a,b,c,g,i,k,n}检测到事件消息,这组消息按最晚发送时间从早到晚排列为{m2,m7,m1,m4,m6,m5,m3}。根据本文提出的算法,为时隙t1内各发送节点选择的接收节点如表1所示。

表1 消息接收节点

3.2.2 并行发送

无线网络是一种共享信道的网络,2个消息同时发送时相互之间可能会产生冲突或碰撞而使消息失真或丢失;无线网络中节点的传输距离和干扰半径均有限,互不干扰的消息可以并行发送,因此消息之间存在干扰性和并行性等特征。网络中各节点发送的消息需基站统一调度,避免信道竞争及消息间的干扰,实现无冲突的消息并行传输。

仍以图1为例,在时隙tn内确定了一组消息的接收节点,选择这组消息中L(i,tn)最小的消息mim优先发送,这是为了让截止期限早的消息能够尽快地传输到基站。同时,为了提高信道利用率,降低传输平均延时,要使这组消息中与mim无干扰的消息并行发送。

首先给时隙t1内所需传输的消息创建一个顶点。然后根据并行消息的判定原则,如果2个消息之间存在干扰,就在这2个消息对应的顶点之间画一条边。这样就得到如图5(a)所示的消息图。

采用图着色理论和禁忌搜索算法,对如图5(a)所示的所有顶点进行多轮条件着色,使得所用的颜色数最少,颜色相同的顶点所对应的消息可以并行发送。着色的基本原则是从最晚发送时间L(i,tn)最小的消息mim代表的顶点开始着色,使用尽可能少的颜色,着色过程中优先选择编号较小的颜色。着色结果如图5(b)所示,只需2种颜色C1、C2即可将消息图着色完毕。在时隙t1内节点b、g、k、n,处在发送状态,节点c、h、l、BS处在接收状态,其他节点处在休眠状态,即链路bc、gh、kl、nBS可以并行传输消息。

图5 时隙t1内消息图和着色结果

基站为每个时隙内所需传输的消息都进行路径选择和并行调度,直到所有消息都能成功传输到基站,相应的并行调度表也构建完成并下传给各个节点。表2是基站为以图1为例的一组消息构建的并行调度表。

表2 消息并行调度

3.3 传输阶段

传输阶段细分为多个时隙,各节点根据自己在调度表中分配的时隙传输消息,没有分配时隙或者对应时隙内不需要调度的节点则进入休眠状态,节约能量消耗。

4 实验仿真

网络仿真可以解决大多数研究人员因没有条件搭建对部署环境及硬件成本很高要求的大规模传感器网所带来的困扰。当前主要网络仿真软件有NS2、OPNET、GloMoSim、OMNeT++等。NS2是一种开源的网络仿真软件,它拥有的模块几乎囊括网络技术的所有方面。使用NS2可以很容易进行网络技术开发,目前已成为广泛使用的一种网络模拟软件,因此本文选取NS2作为协议的网络仿真软件。实验部分Tcl脚本代码如下:

set n(0) [$ns node]

$n(0) random-motion 0

$n(0) set X_ 100.0

$n(0) set Y_ 100.0

$n(0) set Z_ 0.0

$ns initial_node_pos $n(0) 60

set n(1) [$ns node]

$n(1) random-motion 0

$n(1) set X_ 300.0

$n(1) set Y_ 100.0

$n(1) set Z_ 0.0

$ns initial_node_pos $n(1) 60

set n(2) [$ns node]

$n(2) random-motion 0

$n(2) set X_ 500.0

$n(2) set Y_ 100.0

$n(2) set Z_ 0.0

$ns initial_node_pos $n(2) 60

set udp0 [new Agent/UDP]

$ns attach-agent $n0 $udp0

set null0 [new Agent/Null]

$ns attach-agent $n(2) $null0

$ns connect $udp0 $null0

set cbr0 [new Application/Traffic/CBR]

$cbr0 attach-agent $udp0

4.1 实验参数

对于算法的验证选用NS2作为实验仿真平台,从消息截止期限失去率、网络平均延时和能量消耗3个方面来评估算法的性能。本文将实验场景均匀划分成10 m×10 m的网格,各个网格中只有一个节点,节点位置固定不再变化,节点和网络的主要实验参数配置如表3所示。

表3 基本参数设置

4.2 对比分析

本文研究采用截止期限失去率、平均传输延时和节点能量消耗作为主要网络性能评价指标,将本文提出的RMPS算法与经典HEED算法、L-RQS算法和CC-TDMA算法对比分析,来评估RMPS算法的性能。

截止期限失去率定义为未能在截止期限之前到达目的节点的消息占总发送消息数的比率。在本文中将这一评价作为事件驱动的无线CPS网络实时消息调度的重要参考指标。截止期限失去率对比结果如图6所示。当消息数目小于10时,4种算法都能满足消息的截止期限要求;当消息数目大于10时,经典HEED算法截止期限失去率最高,L-RQS算法次之,RMPS算法最低;当消息数目大于90时,经典HEED算法、L-RQS算法和CC-TDMA算法截止期限失去率都会明显升高,而RMPS算法只是略有上升。这是因为在RMPS算法中将消息的截止期限作为网络的首要因素,让截止期限早的消息优先发送,同时,在着色阶段使用尽可能少的颜色为一组消息对应的消息图进行着色,实现无干扰消息并行调度,提高了信道利用率,减少了排队延时。

图6 一轮循环内截止期限失去率

假定事件传输延时为从节点检测到事件到事件成功传输至基站的时间间隔。网络平均传输延时即为一轮循环内所有事件的平均传输延时。平均延时对比结果如图7所示。随着网络负载的增加,4种算法的平均延时都在增加,但相比于HEED算法和CC-TDMA,RMPS算法和L-RQS算法网络的平均延时明显偏低且增长幅度较慢,且在网络负载较高时RMPS算法平均延时表现依然较好。这是因为RMPS算法采用图着色理论,对消息图进行多轮条件着色得到一个最优的解,让尽可能多的消息并行传输,提高了信道利用率,降低了网络平均延时。

图7 平均延时比较

由于传感器节点能量有限,且不能及时补充,因此节点能量有效利用率是MAC协议需要考虑的一项因素。平均能量消耗对比如图8所示。当消息数目较少时,4种算法能量消耗没有明显差别;随着消息数目的增加,RMPS算法和CC-TDMA算法比经典HEED算法和L-RQS算法能量消耗低,而RMPS算法又比CC-TDMA算法低。这主要是因为RMPS算法在选择传输路径时,将节点剩余能量作为一个重要因子,选择剩余能量较高节点作为中继节点。在传输阶段,各节点根据消息并行调度表中分配的时隙确定自己的状态,没有分配时隙的节点使其较长时间处于休眠状态,减少能量消耗。

图8 一轮循环内平均能量消耗比较

5 结束语

本文针对事件驱动型无线CPS实时性要求较高的特点,从并行消息的判定、消息传输的路径选择和消息的并行传输三方面进行研究,建立有效的实时消息调度并行优化模型,并使用图着色理论求解。实验结果表明,本文方法可实现无干扰消息并行发送,提高信道利用率,降低端到端的延时,对无线CPS实时消息的研究具有一定的借鉴意义。

[1] 何积丰.信息物理融合系统[J].中国计算机学会通讯,2010,6(1):25-29.

[2] 李仁发,谢 勇,李 蕊,等.信息-物理融合系统若干关键问题综述[J].计算机研究与发展,2012,49(6):1149-1161.

[3] YOGARATHINAM A.CPS:Architecture and Distributed Computation in the Networked Control Paradigm:An Autonomous Grid Example[EB/OL].[2015-10-12].https://www.researchgate.net/publication/295010727_cps.

[4] IMRAN Q,ALESSANDRA B,ETIENNE B,et al.Modeling Methodologies for Cyber-physical Systems:Research Field Study on Inherent and Future Challenges[J].Ada User Journal,2015.

[5] ZIMMER C,BHAT MUELLER F,et al.Intrusion Detection for CPS Real-time Controllers[J].Power Systems,2015,79(1):329-358.

[6] RAJKUMAR R,LEE I,SHA L,et al.Cyber-physical Systems:The Next Computing Revolution[J].Strasbourg,2010,14(6):731-736.

[7] LEE I,SOKOLSKY O,CHEN S,et al.Challenges and Research Directions in Medical Cyber-physical Systems[J].Proceedings of the IEEE,2012,100(1):75-90.

[8] RAHMAN S U,AHMAD M,BAZAZ S A.A New Energy-efficient TDMA-based MAC Protocol for Periodic Sensing Applications in Wireless Sensor Networks[J].International Journal of Computer Science Issues,2012,9(4):215-222.

[9] YOUNIS O,FAHMY S.HEED:A Hybrid,Energy-efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[10] GUGLIELMO D D,RESTUCCIA F,ANASTASI G,et al.Accurate and Efficient Modeling of 802.15.4 Unslotted CSMA/CA Through Event Chains Computation[J].IEEE Transactions on Mobile Computing,2016,15(12):2954-2968.

[11] BURATTI C,VERDONE R.L-CSMA:A MAC Protocol for Multi-hop Linear Wireless(Sensor) Networks[J].IEEE Transactions on Vehicular Technology,2016,65(1):251-265.

[12] HUANG P K,LIN X.Achieving Optimal Throughput Utility and Low Delay with CSMA-like Algorithms:A Virtual Multichannel Approach[J].IEEE/ACM Transactions on Networking,2015,23(2):505-518.

[13] HAI V L,TANG X.An Efficient Algorithm for Scheduling Sensor Data Collection Through Multi-path Routing Structures[J].Journal of Network & Computer Applications,2014,38(2):150-162.

[14] SEVANI V,RAMAN B.HTTPDissect:Detailed Performance Analysis of HTTP Web Browsing Traffic in TDMA Mesh Networks[J].IEEE Transactions on Mobile Computing,2016,15(4):853-867.

[15] SAMI M,NOORDIN N K,KHABAZIAN M.A TDMA-based Cooperative MAC Protocol for Cognitive Networks with Opportunistic Energy Harvesting[J].IEEE Com-munications Letters,2016,20(4):808-811.

[16] ZHANG R,CHENG X,YANG L,et al.A Novel Centralized TDMA-based Scheduling Protocol for Vehicular Networks[J].IEEE Transactions on Intelligent Transportation Systems,2015,16(1):411-416.

[17] 田立勤,张 琪,陈振国.一种保障无线传感器网络信息实时传输的调度方法:CN103532877A[P].2014-01-22.

[18] JAIN V,AGARWAL S,GOSWAMI K.Dynamic Multilevel Priority Packet Scheduling Design for WSN[C]//Proceedings of International Conference on Signal Propagation and Computer Technology.Washington D.C.,USA:IEEE Press,2014:86-90.

[19] 蒋 青,任行帆,张佳星.一种基于优先级的异构无线网络切换算法[J].重庆邮电大学学报(自然科学版),2014,26(6):826-831.

[20] LING Q,YAN J,DENG H.A Novel Energy-aware Routing Algorithm for Wireless Sensor Networks Based on CDMA and TDMA[J].Ad Hoc & Sensor Wireless Networks,2015,26(1):21-41.

[21] CHIPARA O,LU C,ROMAN G C.Real-time Query Scheduling for Wireless Sensor Networks[J].IEEE Transactions on Computers,2013,62(9):389-399.