IWSNs中的混合式共享链路调度

芦 娜，栗雪娟，吴静松

(1.安阳工学院 计算机科学与信息工程学院，河南 安阳 455000； 2.西安建筑科技大学 理学院，陕西 西安 710000)

0 引 言

工业无线传感器网络(industrial wireless sensor networks，IWSNs)有助于提高工厂的灵活性和可重构性，使得移动子系统或设备能够互连[1]。尽管工业自动化和控制应用的无线HART[2]和ISA100.11a[3]标准的发展迄今已取得了重大进展，但IWSNs在确保工业应用的可靠性和延迟性能要求方面仍然面临着重大挑战[4]；无线HART和ISA100.11a基于IEEE802.15.4物理层和MAC层，共享一些基本的无线技术和机制[5]，如集中式网络管理和结合跳频的时分多址(time division multiple access，TDMA)[6]。在这两种标准中，调度方案对于确保IWSNs中信息的可靠和低延迟传输至关重要；但无线HART和ISA100.11a标准没有指定任何链路调度方案，而只是定义了一些必须满足的要求。这些要求之一就是调度方案必须每跳分配至少3个链路，以便在给定的传输截止期限之前尝试传输每个消息。无线HART标准还规定，在一个时隙内，不能在两个不同的信道中安排任何设备处于接收模式。

对于多跳无线传感器网络(wireless sensor networks，WSNs)的研究提出了集中式和分布式调度方案[7,8]。分布式方案从原理上讲可以更好地应对网络运行和动态变化[9]。文献[10]提出的方案利用节点从其本地邻域获得的信息来分配链路；在文献[11]提出的分布式方案中，目的节点根据源节点生成的流量特性负责分配链路。尽管分布式方案通常比集中式方案能提供更大的灵活性和适应网络条件的能力，但不适合于具有严格可靠性和延迟要求以及利用集中式架构和网络管理的IWSNs[12]。

在集中式方案中，全部调度决策由一个中心节点执行，其余节点仅负责信息的无线传输和接收，以及一些有限的数据处理功能。文献[13]提出了一种基于路由图的链路调度方案；文献[14]提出在一组源和目的节点之间分配信息传输链路，寻求确保全部传输截止期限都得到满足，同时避免并发传输之间的冲突；文献[15]研究了IWSNs中控制平面的逻辑控制功能、数据平面的数据转发过程、协议栈的跨层调度、网络资源抽象及调度策略。总之，大多数集中式调度方案都专注于考虑源和目的节点之间多种可能路径的链路调度问题。

对此，本文针对IWSNs提出了一种链路调度方案。方案利用属于同一路径或多跳路由的节点间的共享链路，路径中的消息传输充当一个虚拟令牌，以确定允许哪个节点在共享链路中的每个时间点传输，从而允许灵活分配和使用链路，因此具有更好的防止传输差错和减小延迟的能力。结果表明，与现有的IWSNs链路调度方案相比，本文方案不仅可以提高可靠性和延迟性能，还能更有效地利用链路。

1 本文提出的混合式链路调度方案

1.1 两种典型的集中式链路调度方案

对于单个路径的调度，目前存在2种普遍采用的集中式链路调度方案，本文将这两种方案作为参考和加以比较的基础；第一种方案连续分配路径每跳使用的全部链路，包括将信息从路径中一个节点传输到下一个节点的初始链路，以及信息在第一次传输失败时潜在重传的附加链路，将这一方案称为逐跳(hop by hop，HbH)，其工作原理如图1(a)所示，它表示源和目的节点之间3-跳的主路径(用变量H表示跳数)。根据无线HART，在源和目的节点之间的主路径中，必须为每跳分配2个链路，图1(b)为应用HbH得到的链路调度。第一个链路分配给信息的初始传输，第二个链路分配给初始传输失败时的潜在重传。在这种情况下，从节点A到节点B的信息传输将利用第一个链路l1，接下来的链路l2被预留用于从节点A到节点B的同一信息的可能重传，以防节点B不能成功接收初始传输。遵循同样的原理，接下来的两个链路预留作为节点B与节点C之间的跳，等等；只要每跳的传输差错数小于为每跳预留的链路数，HbH方案就能成功地将信息传输到目的节点。但这种方案即使在不存在传输差错的情况下，将全部链路按顺序规划分配给每跳会增加延迟；本文把第二种方案称为RTE。方案首先为每跳的初始信息传输分配链路，然后为可能的重传分配链路。对于图1(a)的示例，RTE将第一个链路l1分配给从节点A到节点B的信息传输，如图1(c)所示，将链路l2分配给从节点B到节点C的同一信息的传输，等等。然后将链路l4、l5和l6预留分别作为从节点A到节点B、从节点B到节点C和从节点C到节点D的可能信息重传。在没有传输差错的情况下，RTE方案减少了传输信息的时间，但也降低了向目的节点传输信息的可靠性。例如，如果用l1将信息从节点A传输到节点B失败，则不能使用链路l2和链路l3，因为从节点A到节点B的信息重传(链路l4)是在l2和l3之后。如果使用l4重传成功，则节点B和节点C将各只有一次尝试(使用链路l5和l6)成功将信息传输到节点D。

图1 两种典型的集中式链路调度方案

针对上述2种典型的集中式链路调度方案存在的不足，本文提出一种链路调度方案。方案利用HbH和RTE方案的优势，同时避免其缺点。提出的方案将共享链路集中分配给属于同一路径的节点，但至于哪些节点应当在每个时间点使用共享链路的决策又是分布式的。为简化起见，将本文提出的方案称为混合式共享链路调度方案(hybrid shared link scheduling scheme，HSLSS)。HSLSS提供了根据实际链路质量条件调整链路调度和利用的能力，不仅可以降低工业应用所要求的延迟，同时还可保持高可靠性。

1.2 HSLSS工作原理

为了阐明其工作原理，仍考虑图1(a)所示示例，并定义R为完整路径允许的消息重传总数。在传输开始，除源节点外，路径中全部节点都处于接收模式，但每个节点以不同的链路进入接收模式，如节点B在l1中进入接收模式，而节点C和节点D分别在l2和l3中进入接收模式。节点应当保持以下R条链路的接收模式，直至它们正确接收需要传输到目的节点的消息。当一个节点正确接收消息时，它会将消息传输到多跳路由中的下一个节点。源节点分配R+1条链路发送消息，目的节点分配R+1条链路接收消息。路径中全部中继节点(即图1(a)中节点B和节点C)分配R+2条链路接收和发送消息，如图2所示。中继节点在它正确接收到来自前面节点的消息前，不能使用任何分配的链路进行传输。路径中每跳都与其前跳共享R条链路。图2表明了HSLSS如何为图1(a)情形(路径中H=3跳)分配不同的链路，完整路径允许的消息重传总数(R)等于1、2和3。图中给出了当R分别等于1、2和3时，HSLSS为完整路径分配4、5或6条链路。如果R=H，则HSLSS使用与HbH和RTE相同数量的链路。如果R1时，l3被节点A、节点B或节点C共享，用于消息的潜在传输，但单个节点能够在给定的时间点通过共享链路传输消息，并且消息充当虚拟令牌来确定哪个节点可以通过共享链路传输。为了说明这个原理，考虑R=3的例子，假设从节点A到节点B使用l1的消息首次传输是错误的，这时，可用l2作为消息从节点A到节点B的消息传输，即节点B保持接收模式，而不使用链路传输到节点C。如果第二次传输正确，则节点B使用l3将消息传输到节点C，而节点C和节点D处于接收模式，如果第二次传输是错误的，则节点A将使用l3第三次尝试将消息传输到节点B，如果这次传输是正确的，则节点B将使用l4将消息传输到节点C。过程继续进行，直至目的节点接收到消息或达到完整路径允许的消息重传总数(R)为止。

图2 当R=1、2和3时，HSLSS对有3-跳路径的 链路调度原理

只要在路径的全部跳的传输差错总和等于或小于完全路径允许的消息重传总数(R)，则HSLSS就可以确保消息可靠地传输到目的节点，这个特性独立于传输差错发生的特定跳。此外，在无传输差错的情况下，HSLSS可以在相当于H个链路的时间内向目的节点传输消息。尽管RTE在无传输差错的情况下可以确保相同的延迟，但只有当传输差错总数小于分配给每个节点的传输链路数时，才能确保消息正确传输到目的节点。HbH在无传输差错的情况下需要比HSLSS和RTE更多的时间将消息传输到目的节点，此外，只有当每跳的传输差错数小于分配给消息传输的每跳的链路总数(包括重传)时，HbH才能确保消息正确地传输到目的节点；在存在传输差错的情况下，HSLSS也可以最小化消息传输到目标节点的时间，因为它不会延迟重传。RTE不能最小化传输消息的时间，因为重传需要等待总共H条链路。HSLSS还能最大化分配给路径或多跳路由的给定数量链路(H+R)的可靠性，因为只要传输差错数等于或小于R，HSLSS就可以将消息传输到目的节点。如果存在R+1个差错或更多，则不存在有H+R条链路的方案可以将消息传输到目的节点，因为它将需要H+R+1次传输。

1.3 性能指标建模及分析

采用2个主要性能指标来评价方案的性能。一是用端到端数据包交付比(end-to-end packet delivery ratio，PDRE2E)来度量链路调度方案的可靠性，计算为目的节点正确接收到的消息数与源节点发送的消息总数之比；二是用端到端交付延迟(end-to-end delivery delay，DDE2E)来度量链路调度方案的延迟性能，计算为源节点发送消息与它的目的节点接收之间经过的平均链路数，且该计算时只考虑在目的节点正确接收到的消息；另外定义一个利用链路平均百分比指标来评价调度方案的效率，为在多跳路由中用于传输消息使用的链路数与为该路由分配的链路总数之比。

下面主要对在源节点和目的节点之间具有H-跳的路径或多跳路由来得到2个主要性能指标—可靠性和延迟性能的解析表达式。

1.3.1 可靠性

用PDRi表示跳-i上的PDR。如果考虑每跳上稳定的PDR，则PDRE2E可以从解析上进行计算；在下一跳的链路之前，HbH将全部链路分配给给定的跳(包括用于重传的链路)。在跳-i正确传输一个消息的概率Pi计算为

Pi=1-(1-PDRi)Li

(1)

式中：Li表示分配给跳-i的链路数。考虑在路径每跳得到的PDRi是相互独立的，这时，对于HbH来说，就可以用式(1)来计算PDRE2E

(2)

RTE首先为每跳的初始消息传输分配链路，然后为潜在重传分配链路。将P0-rtx定义为在从源到目的节点路径中不需要任何重传消息到达目的节点的概率，则P0-rtx可计算为

(3)

将Prtx-h定义为消息在跳-h重传后到达目的节点的概率，则Prtx-h可以计算为

(4)

式中：(1-PDRh)表示消息第一次在跳-h不正确传输的概率，且需要重传。可以将概率P1-rtx计算为消息在路径H-跳的任何一跳单次重传后在目标节点正确接收的概率，这个概率等于路径中全部H-跳的Prtx-h概率之和

(5)

则对于RTE，PDRE2E计算为

(6)

对于HSLSS，可以得到PDRE2E的解析表达式为R的函数。当R为1时(即只允许1次重传)，如果没有传输差错(即式(3)的P0-rtx)或只有1次传输差错(即式(5)的P1-rtx)，则消息传输到目的节点。当R=1时，则HSLSS的PDRE2E是P0-rtx和P1-rtx的和，其值由式(6)表示。当R=2时，如果总共有2次重传，则消息也可以传输到目的节点。根据确定P1-rtx相同的过程，可以计算2次重传后目标节点正确接收消息的概率P2-rtx为

(7)

按照同样的过程，可以计算P3-rtx

(8)

最后，HSLSS的PDRE2E可以表示为R的函数：

当R=1时

(9)

当R=2时

(10)

当R=3时

(11)

1.3.2 延迟性能

如果考虑每跳i的PDRi是不变的，则可以从解析上得到DDE2E为源节点和目的节点之间的跳数H的函数。

根据1.1节的分析，对于HbH，DDE2E指标可以计算为两个延迟分量DD0和DD1的和。DD0为消息到达目的节点而在最后一跳不需要重传时所经过的端到端延迟，DD1为消息在最后一跳重传之后到达目的节点时所经过的端到端延迟。DD0是通过将消息到达最后一个中继节点的概率乘以消息在最后一跳不需要重传正确到达目的节点的概率(PDRH)并乘以相应的延迟2(H-1)+1，然后将这个乘积结果除以PDRE2E得到。DD1是将消息到达最后一个中继节点的概率乘以消息在最后一跳重传输后正确到达目的节点的概率(PDRH)并乘以相应的延迟2H，然后将这个乘积结果除以PDRE2E得到。则DDE2E可以计算为

(12)

对式(12)简化并得到仅依赖于PDRH和H的HbH的DDE2E为

(13)

RTE的DDE2E可计算如下

(14)

式(14)中的第一项等于概率P0-rtx乘以相应延迟(H)并除以PDRE2E，第二项等于概率P1-rtx乘以相应延迟(2H)并除以PDRE2E。

HSLSS的DDE2E可得到为R+1项之和：

当R=1

(15)

当R=2

(16)

当R=1时，式(15)中的第一项为概率P0-rtx乘以相应的延迟(H)并除以PDRE2E的结果，第二项为概率P1-rtx乘相应的延迟(H+1)并除以PDRE2E的结果；当R=2时，得到的DDE2E为式(15)的前两项加第三项即概率P2-rtx乘以其相应的延迟(H+2)并除以PDRE2E。按照同样的过程，可得到更大R值的DDE2E。

2 性能评价

2.1 实验设置与环境

将本文提出的链路调度方案与HbH和RTE方案得到的性能进行比较来评价本文提出的链路调度方案。全部方案在4种多-跳情形下进行分析，如图3所示。

图3 评价的4种情形

第一种情形考虑一条路径或H=3的多跳路由，且每跳中有相同的PDR(即PDRAB=PDRBC=PDRCD)。通过改变每跳的PDR，来分析所提出方案在不同链路质量下的性能；第二种情形将跳数扩展到4，并考虑每跳相同的PDR(即PDRAB=PDRBC=PDRCD=PDRDE)，来研究源节点和目的节点之间的跳数对链路调度方案性能的影响；第三种情形考虑每跳具有不同PDRi的更实际的情形，来评价链路调度方案的性能；第四种情形考虑一个移动节点A，它在节点B的无线电覆盖范围内移动，来评价由于节点的移动而产生的可变链路质量条件下链路调度方案的性能。对于4种情形，节点A和节点B之间的最大距离(dAB)设置为150 m，也考虑静态节点间的两个距离值(50 m和150 m)。

对于仿真，所有参与链路调度过程的函数都在Matlab中实现。考虑节点集成XDM2510H无线HART无线电收发器[16]，无线电收发器采用3.6 V电源供电，在传输和接收模式下，功耗分别为18 mA和6 mA，传输功率为8 dBm，接收机灵敏度为-90 dBm。

2.2 实验结果

2.2.1 情形1

图4为情形1和R设置为1、2、3和4时得到的结果(将这时的HSLSS方案分别记为HSLSS1、HSLSS2、HSLSS3和HSLSS4)。

图4 可靠性和延迟作为PDRi的函数

从图4(a)可以看到，对于全部可能的PDRi值，HSLSS2和HSLSS3优于其它方案。这意味着HSLSS可以获得比HbH和RTE更高的PDRE2E。所得结果还表明，降低PDRi值对HSLSS的影响小于其它方案。例如，当PDRi=0.95时，HSLSS3获得的PDRE2E=0.9999，而HbH和RTE获得的PDRE2E分别为0.9925和0.9860。当PDRi减小到0.75时，HSLSS3可以保持较0.9624的较高PDRE2E，而HbH和RTE的PDRE2E分别显著下降为0.8240和0.7383；还可看到，HbH获得比RTE更高的PDRE2E，这是因为HbH允许在路径的每跳进行可能的重传，而RTE只允许在完整路径中进行一次重传；图4(b)表明，HbH有较高的DDE2E，这是因为HbH只能在l5上向目的节点传输消息(即使没有传输差错)，而其它方案可以在l3上进行。因此，对于HbH，最小可能延迟DDE2E为5，而对于其它方案，最小可能延迟DDE2E为3。正如预期的那样，RTE相比于HbH减小了延迟，但与HSLSS方案的全部配置包括采用与RTE相同的链路总数配置(即HSLSS3)相比，RTE增大了延迟。

图5为传输消息所用链路的平均百分比作为PDRi的函数。可以看到，HSLSS运行总比HbH和RTE更高效，获得了更高的分配链路的平均利用率；从图5的结果还可以发现，方案HbH和RTE在低PDRi值(0～0.2之间)下运行时，链路利用率较低(约33%)，这表明很少消息被传输到目的节点，实际上甚至很少有消息到达路径的第二跳；图5还表明，当对于完整路径使用较小数量的链路，在高PDRi值(0.9～1之间)下，HSLSS可以提高使用链路的平均百分比，HSLSS1比HSLSS2和HSLSS3有更高的利用率。这是因为在较好的无线电链路质量条件下，消息通常不需要重传到达目标节点。

图5 平均链路利用百分比作为PDRi的函数

2.2.2 情形2

情形2相对于情形1在路径中增加了额外的跳，如图3所示。这时，HbH和RTE每跳分配2个链路，因此对于完整路径总共分配8个链路。结果如图6所示。从图6(a)可见，当至少有2个共享链路用于重传且H等于或小于4时，HSLSS优于HbH和RTE。相比于其它方案，HSLSS获得的PDRE2E增益随着跳数的增加而增加。例如，当PDRi=0.95时，HSLSS3获得的PDRE2E=0.9998，类似于在情形1获得的PDRE2E=0.9999的性能，而HbH和RTE的PDRE2E性能相比于情形1中的0.9925和0.9860分别下降为0.9885和0.9765；图6(b)表明，DDE2E性能类似于情形1中的DDE2E性能，HSLSS还是优于HbH和RTE。对于全部链路调度方案，尽管延迟随着跳数增加而增大，但HSLSS与其它方案相比，增幅较小。

图6 可靠性和延迟作为PDRi的函数

图7表明，与情形1相比，HSLSS在情形2提高了利用链路的平均百分比，这是因为有更多的共享链路用于重传。

图7 平均链路利用百分比作为PDRi的函数

2.2.3 情形3

情形3仿真了每跳具有可变PDRi的更实际的情形。考虑节点相隔50 m或150 m来模拟PDRi条件。对于H=3的路径，对跳数(8)间的全部可能距离配置进行仿真。dAB、dBC和dCD和分别表示节点A和B、B和C、C和D之间的距离。

表1为不同方案和跳数间距离全部可能配置得到的PDRE2E。从表1可见，HSLSS相比于HbH和RTE，提高了可靠性。结果还表明，当路径包括至少一个长距离跳时，HSLSS3获得的PDRE2E明显高于其它方案。相对于HSLSS3、HSLSS2有轻微的下降，但仍然显著优于HbH和RTE。HSLSS更鲁棒，因为它可以利用有较低PDR的更多长距离跳链路；另一方面，HbH和RTE每跳最多只能利用2个链路，且不依赖于它们的链路质量，同样，获得的PDRE2E依赖于路径中长距离的跳数，但不依赖于它们在路径中的位置。

表1 全部可能距离配置的PDRE2E

表2所示的结果也表明了HSLSS更好的DDE2E性能。值得注意的是，由HSLSS3、HSLSS2和RTE获得的DDE2E依赖于路径中的长距离跳数，长距离跳数越少，延迟就越小。这是因为对于3种方案，每次重传都会增大DDE2E，而独立于需要重传的跳数；另一方面，HbH的延迟性能不依赖于路径中的长距离跳数，而主要依赖于路径中最后一跳的链路质量。事实上对于HbH，只有路径的最后一跳上的重传增加DDE2E。

表2 全部可能距离配置的DDE2E

表3为利用链路的平均百分比。可以看到，当路径中没有长距离跳时，HSLSS3利用的链路类似于HbH和RTE。当这种跳数增加时，HSLSS3相对于HbH和RTE，提高了分配链路的利用率。这意味着当链路质量下降时，HSLSS3使用更多可用链路进行重传，这最终有利于其PDRE2E性能。表3的结果表明，实际上HSLSS2方案获得了更高的分配链路利用率(比HSLSS3高10%)。这是由于与HSLSS3相比，HSLSS2有较少的链路分配给完整路径。这时，当链路质量条件下降时，HSLSS2需要更多地利用可用链路来进行重传，但随着路径中长距离跳数的增加，相对于HSLSS3，它有效克服差链路质量条件的能力降低了。

表3 全部可能距离配置的平均链路利用百分比

2.2.4 情形4

仿真中，节点A以1 m/s的速度朝节点B的覆盖区域周围移动。节点A与B之间的最大距离设置为150 m。还考虑每跳可变的PDRi，节点B和C之间、节点C和D之间50 m或150 m的距离。

图8为得到的全部指标的结果。图8表明，HSLSS即使在移动节点存在的情况下也优于其它方案。R=3的HSLSS配置即HSLSS3获得了最高的PDRE2E如图8(a)所示和最小的DDE2E如图8(b)所示。与HbH和RTE相比，HSLSS3还提高了可用链路的平均利用率如图8(c)所示。具体而言，当链路质量条件(PDRi)降低时，相对于其它方案，HSLSS获得的增益提高了。例如，在配置[50,50]下，HSLSS3相对于HbH，将PDRE2E提高了2%，在配置[150,150]下，改进提高到14%。当链路质量条件降低时，与其它方案相比，HSLSS也有更小的PDRE2E下降。例如，当在最佳配置[50,50]和最差配置[150,150]的链路质量条件下时，HSLSS3的PDRE2E性能仅下降3.4%，而在相同条件下，HbH和RTE的PDRE2E性能分别下降了15.4%和21.4%。HSLSS在克服差链路质量条件下所表现出的能力对于关键应用非常重要，例如需要非常高可靠性水平的工业应用。只要移动节点不离开其连接节点的通信范围，HSLSS就不需要重新调度链路，因为它可以维持较高的PDRE2E水平。

图8 情形4下得到的结果

3 结束语

本文提出并评价了一种有严格可靠性和延迟要求的IWSNs的链路调度方案，并提出了可用于性能计算的可靠性和延迟性能的解析表达式。方案采用属于给定路径或多跳路由的一部分节点间的共享链路，通过路由传输的消息充当虚拟令牌，以确定哪个节点应当在每个时间点使用共享链路。采用共享链路和虚拟令牌可以更灵活地利用可用链路。结果表明，提出的链路调度方案不仅可显著改善现有方案的可靠性和端到端延迟，还能更有效利用链路资源；本文提出的链路调度方案不仅可应用于IWSNs，也可用于其它基于TDMA的集中式多跳无线网络。