无线多跳网络中基于限期约束的报文转发策略研究

刘猛

无线多跳网络中基于限期约束的报文转发策略研究

刘猛

针对有损及存在突发链路的无线多跳网络中的实时报文转发问题进行了研究，目标是尽量提高各报文在限期前到达目的地的概率。假设信道实时状态无法获得，但可以利用真实报文传输的成功率和失败率做出估计，将报文转发问题看成是一个部分可观测马尔科夫决策过程，并获得了可以实现在线报文转发概率最大化的最优转发策略。另外，为了降低实现复杂度，文中还通过利用最大体积内切椭球获得了近似解。仿真实验也验证了本文方案的有效性。

无线多跳网络；报文转发；限期；马尔科夫链；最优转发策略；最大体积内切椭球

0 引言

机器与机器通信是近几年的研究热点[1,2]。然而，很少有文献对满足实时监控等机器与机器应用的QoS要求所必需的基础技术进行研究。其中一项关键要求就是如何在苛刻的报文期限前转发报文[3]。例如，在智能电网中，只有及时接收到包含电压、功率和频率的测量数据（在限期前）才能对生产方和消费方进行协调、检测异常及保证电网稳定性。已有文献量化证明[4]，端到端数据流中报文满足传输限期的概率，对闭环控制系统的性能具有重要影响。

部分文献对非可靠性网络中严格限期条件下的通信问题进行了研究。比如，文献[5,6]中研究了“适时吞吐量”问题。文献[7]构建了面向可重构路由器的报文转发引擎构件重构模型，并基于Pass-Through模式设计实现了可重构FPGA器件与网络处理器相结合的程序／电路构件运行环境。仿真结果表明，可重构路由器报文转发引擎在保证高吞吐率、低延迟的报文转发处理性能的同时，可有效支撑多样化业务构件灵活重构与映射。文献[8]采用状态有限马尔科夫链信道模型，研究了限期约束条件下的最大可靠性数据转发问题。文献[9]研究了限期约束条件下的最小能量数据转发问题。然而它们均假设，系统运行时各个节点上的调度器可以充分访问其出向链路上的信道状态（比如通过运行专门的链路估计器获得）。本文将文献[8,9]的工作扩展到调度器无法访问到出向链路的信道状态这一情景下。此时，只能通过链路上的数据传输来观察链路的信道状态。通过观察突发链路上的内存，可以预测信道的未来状态。文中给出了在这些有限信道状态信息下可以实现在线报文转发概率最大化的最优数据转发策略。同时，给出一种新的计算量较低的近似求解方法，最后通过仿真实验验证了本文方案的有效性。

1 模型和相关假设

本文主要研究非可靠性多跳无线网络上的通信问题。报文通过有向图(N,L)转发，其中节点集合N={1,2,...,N}表示收发两用机，链路(i,j)∈L表示节点i可向节点j发送报文。目的节点表示为N，且节点集合N中的节点均可到达。Ni定义为节点i可向其发送报文的节点集合，Ni表示节点i的出向链路数量。

通过对过程进行时隙处理，每个时隙允许传输一个报文及其相应的确认。通信链路的可靠性较低，链路上的报文丢失事件可模拟为状态有限马尔科夫链。不同链路的马尔科夫链相互独立，且节点无法直接访问马尔科夫链的状态。然而，节点通过在其出向链路上传输数据报文并记录相应结果，就可观察到其任意一条出向链路的状态。每个马尔科夫链在离散时间内演化，且状态变化与时隙边界一致。设s∈S表示链路的马尔科夫状态，S表示所有可能状态的集合。设表示节点i所所有出向链路(i,j)的状态，且当信道状态为s时wij=s。在状态为wij的链路(i,j)上传输报文，则报文成功传输的概率为qwij，失败概率为pwij=1-qwij。

假设在某一场景下，在时间t=0时只产生一个报文，需要在时间t=DD前传输到目的节点N。本文的目的是确定一种转发策略，使得在限期N前成功转发报文的概率最大。本文还研究了所有链路损失过程描述为双态Gilbert-Elliott (GEE)模型时的最优转发策略。这些模型包含“理想”(G)状态和“非理想”(BB)状态，如图1所示：

图1 链路报文损失的双态Gilbert-Elliot (GEE)模型

如果链路的状态较好，则设置wij=GG，否则设置wij=B 。理想状态下的成功概率为1，非理想状态下的成功概率为0。因此，如果已经观察到前一时间的状态为理想状态，则当前时隙的成功传输概率为qG，如果观察到的状态为非理想状态，则成功概率为qB。于是，平均成功概率为（理想状态的静态分布）：。此外，用TB表示非理想状态的平均突发长度（时隙数量），即TB=1/qB。

2 问题定义及其最优解

2.1 限期约束条件下进行数据转发的POMDP问题定义

文献[9]将多跳网络限期约束条件下的报文转发问题看成是有穷界限马尔科夫决策过程（MDP）。系统状态包括报文位置和网络中所有链路的信道状态。通过为限期前成功传输到目的地的报文分配一定奖励，平均奖励则等于限期约束条件下的报文转发可靠性。

因为，节点只能访问网络中链路的部分信道状态（自己的出向链路状态），所以这也是部分可观察马尔科夫决策过程（POMDP）。此外，本文假设通过在网络中进行真实的数据传输即可获得链路的信道状态。数据传输之后，可以根据链路的马尔科夫链模型估计将来信道状态的概率分布。GEE模型处于理想状态时的概率更新示例如图2所示：

图2 GE模型的理想状态概率更新。平均理想状态概率为0.5，时间为0时只能观察到理想状态(G)或非理想状态(B)。

文献[10]已经证明，置信状态（即系统状态的概率分布）是PPOMDP问题的充分统计量，且最优转发策略是置信状态到行为的一个映射。具体来说，节点需要维护其出向链路信道状态的概率分布。其他链路的置信度是一致的，且等于平均信道状态分布，因为，该节点无法访问其他链路的信道状态。这一结论可以将POMDP问题化简为连续状态空间条件下的等效MDP问题。因此，可以相应确定价值函数和Bellman等式。

假设价值函数（即限期约束条件下的最大转发可靠性）为Ri(t,b)，其中t表示当前时间，表示节点i在先前时隙期间出向链路的所有可能信道状态的置信度。本文隐含地假设节点i其他链路的置信度处于其平均状态。向量b的长度为（因此，当用GE模型描述链路损失时，b的长度为于是对所有节点i有

其中wi表示先前时隙t-1的信道状态；表示当前时隙t的信道状态；Rj(tt+1)表示平均信道状态分布条件下节点j在时间t+1时的最大可靠性；表示观察到信道状态时的新的置信度。使用平均信道状态分布的可靠性RRj(t+1)，是因为节点i无法访问节点j的出向链路状态。可由链路的马尔科夫链模型计算出来。最后，价值函数可计算为公式（2）：

本文的目标是计算报文由源节点在时间0生成时的价值函数RRsrc(0,b)。

2.2 最大可靠性和最优策略

因为，系统状态是连续的，所以，无法使用标准的离散时间动态规划求解公式（2）。然而，有穷界限POMMDP问题的价值函数是置信状态上的分段线性凸函数(PWLLC)[10]，即Ri(t,b)可写为公式（3）：

其中集合Γi,t在每次更新时计算。通过展开BBellman更新即可证明PWLC属性。当初始条件为RN(t,b)=1,∀t,b和Ri(D,b)=0,∀b,i≠NN 时，对时间tt=D-1到t==0期间的每个节点运用更新。为了更详细地确定更新和最优策略，考虑随机节点i。对时间t=D,D-1,...,D-hi-1，可靠性均为0，其中hi表示与目的地之间的最小跳数距离。t=D-hi，则有公式（4）：

Rj(D-hi+1)在前一步骤t=D-hi+1中节点j计算得到，且Ri(D--hi+1,b)=0,∀bb 。因此，对t=D-hi，价值函数具有如下PPWLC属性：

下文通过归纳法来证明当PWLCC属性在时间t+1成立时，在时间t也成立。设表示新的信道状态置信度，使用贝叶斯规则来计算新的信道状态的置信度。如公式（5）：

其中，如果新的信道状态w˜i与链路(i,j)的wwi'j相等，则1{wi'jw˜i}=1，否则为0。因此，得公式（6）：

上式利用了如下归纳假设：Ri==(t+1,b')是置信状态b'上的PPWLC函数。将这些表达式代入式（1），有：

将其进一步化简为公式（7）：

因此，限期约束条件下的最大可靠性为公式（8）：

该式表示置信度为b时的PWLCC属性。每个α向量关联一个行为，通过确定最大化时的α向量即可求得最优行为。可以发现，当界限长度增加时，α向量数量呈指数增长。请注意，每个节点i的行为数量为，信道可能状态数量为。因此，。对第2节描述的GE模型，向节点j传输数据时的最大转发可靠性为公式（9）：

GE模型有两个信道状态，但是，理想状态下的损耗概率为0。这表明，，远小于通用马尔科夫链路模型。在下文中，只研究双态GE模型。然而，所得结果可直接扩展至通用型有限状态马尔科夫链模型如图3所示：

图3 LLP修剪示例。虚线被修剪，因为它在任何置信度下均没有获得最优值。

2.3 基于线性规划的修剪处理

每次Belllman更新时，α向量数量均会上升，且定义最终价值函数的线性函数数量可能会很大。然而，在价值函数的PWLC表示中，可能存在部分向量α∈Γi,t对所有置信度均非最优。修剪这些冗余向量，以节约后续更新时的计算开销。

基本的修剪方法就是通过线性规划((LP)来确定α向量是否有用，如果冗余则将其删除。对Γi,t中的所有α向量运行这一步骤。向量αm的线性规划具体内容如公式（10）：

最大化：δ条件：αmm·b-α·b≥δ,∀α∈Γi,t{αm}, （10）

该线性规划可确定向量αm相比于其他所有向量，可为价值函数贡献的最大额外价值。如果线性规划返回δ≤0，则向量δ≤0受其他向量主导，应被修剪。例如，图3中虚线的最大额外价值为负，证明它受其他线性函数主导，可以被修剪。

3 最大体积椭球修剪近似解

在运行期间，每个节点运行的数据转发算法通过计算当前置信度和每个α向量间的内积来寻找该时隙期间的最优行为，如公式（3）所示。考虑到机器与机器应用场景中的硬件平台往往为资源有限平台，如果α向量数量较大，则难以在这些平台上存储并计算这些最优行为。本节提出一种近似求解方法，在降低部署复杂性的同时（降低了α向量的数量），又维持了优异性能如图4所示：

图4 向量为α1且体积较大时的MVE修剪示例。

粗垂直线表示α1和α2的额外价值（即线性规划时的δ）。这些价值比较接近，但是本文更倾向于α1，因为它的置信度活跃区间更大。

2.3节的修剪策略保存了贡献值为正δ的α向量。一种直观的近似求解方法是根据其δ值对α向量排序，将贡献较小的向量去除。然而，线性规划方法没有返回α向量居于主导地位的置信范围。例如，在图4中，向量α1和α2的δ贡献值比较接近，但是α1的活跃范围更大。本文提出根据向量居于主导地位的区域的最大体积内切椭球(MVE)尺寸来对向量排序。椭球的体积可高效计算出来，作为α向量居于主导地位的区域的真实体积（该体积难以计算）。在图44中，必要情况下，α2的椭球较小因此可被首先修剪。

对向量αm∈Γi,t，其居于主导地位的区域是维线性空间的多面体Pm。设表示该空间中的一个点，且b表示信道状态的置信度，r表示转发可靠性。定义且ek作为第k个元素为1、其余元素均为0的向量。多面体Pm可描述为：

该式可写为如下一组线性不等式：

根据文献[11]]可知，寻找最大体积内切椭球是个凸优化问题：

最大化logdetB

其中B表示描述椭球的对称矩阵，椭球的体积与数学行列式B成正比。为了求解该问题，下面给出了一种简单的启发式算法。该算法首先通过线性规划修剪掉冗余向量，然后迭代修剪掉体积最小的α向量，直到所有α向量相对于最大体积的体积大于阈值为止如算法1：

算法1：阈值为ξ的MVE修剪

RRN(t)=1∀t∈[0,D];Ri(D))=0∀i≠N

FFor t=D-1到0 do

For 所有i∈NN及i≠N doo

利用式（8）计算α向量

使用式（10）及线性规划修剪掉冗余的α向量

计算每个α向量的MVE体积det(B)

Whilemmin(det(B))/max(det(B)))≤ξ do

删除体积最小的α向量

计算每个α向量的MMVE体积det(BB)

End whilee

计算平均置信度为Ri(t)的可靠性

End for

EEnd for

4 仿真实验

我们通过MATLAAB仿真和简单网络证明本文方法的有效性，如图5所示：

图5 网络拓扑示例

在本节中，统一用节点1表示源节点，节点16表示目的节点。链路上的报文消除服从GEE模型，所有链路的模型参数相同，平均成功概率为πG=0.5。

图5首先比较了本文所研究的在信道状态信息有限条件下，带有限期约束时的最大可靠性，此时前一时隙所有出向链路的信道状态已知。当报文注入网络时，假设无先验传输历史信息，因此，使用平均信道状态置信度进行报文转发。只知道有限信道状态信息时的限期约束可靠性始终低于知道完全的信道状态信息时如图6所示：

图6 完全信道状态信息和最小平均延时路径两种情况下的限期约束可靠性比较。

如果链路的突发性较弱且TB=22.5，则知道完全状态信息的效果将会下降。原因是此时成功传输概率基本与前一时隙的链路状态无关。

在图6中比较了信道状态信息有限时限期约束条件下的最大可靠性与平均最小延时条件下的可靠性。因为，链路为同质链路，所以，网络中的任意三跳路径均是最小平均延时路径。图6表明，除非限期时间为3，否则最小平均延时路径的性能始终低于有限价信道状态。此时，限期时间等于最小跳数，在当前报文的转发决策中无法使用获得的信道状态。

限期约束条件下的最大可靠性取决于信道状态知识。如果报文注入网络的频率加剧，则能获得更多的信道状态最新信息，进而提升端到端可靠性。3种不同注入率条件下的最大可靠性如图7所示：

图7 报文注入速率对限期约束最大可靠性的影响。注入率越高，可靠性越高。

当采用高速和中速注入率时，分别在每一个限期周期和两个限期周期内注入报文。从图7中可以看到，注入率越高，可靠性越高。然而，当限期变长时，3种情景下的差异消失。原因是此时链路的信道状态置信度与下一报文注入前的均值比较接近。

最后，算法1中阈值ξ取不同值时，进行MVVE修剪的近似求解方法的限期约束最大可靠性如图8所示：

图8 平均信道状态置信度条件下的限期约束可靠性：MVVE修剪策略近似解

最优转发策略和MMVE修剪转发策略每个节点的α向量平均数量，如表1所示：

表1 MMVE修剪取不同ξ阈值时，每个节点的α向量平均数量

此时限期时间为10。结果表明，ξ较大时，被修剪的α向量较多，可靠性较低。当ξ=1时，每个节点每个时间只有一个α向量，但是可靠性仍然远高于最小平均延时路径。此外，当ξ=1e-5时，MVE修剪策略虽然只使用一半的α向量，但性能只有轻微下降。

5 总结

本文研究了多跳无线有损网络限期约束条件下的报文转发可靠性最大化问题。将链路上的报文丢失模拟为状态有限马尔科夫链，只有通过在链路上传输报文才能获得链路的状态。将该问题阐述为部分可观察的马尔科夫决策过程，并获得了最优策略。引入一种新的基于最小体积内切椭球的修剪方法，以便在性能和部署复杂度间进行折衷。讨论了最大可靠性和最优策略的结构属性。下一步研究包括如下几个方面。首先，可以研究另一种模型，允许节点通过消耗一定能量明确地查询信道来获得链路状态。POMMDP框架可以包括多种查询方法。其次，在低功耗无线传感器网络节点上部署最优策略，然后在测试床实验中评估其性能。

[1]Lu R, Li X, Liang X,et al. GRS: Thhe green, reliabbility, and secuurity of emerginng machine tomachine commmunications[J]. Communiications Magaazine, IEEE, 22011, 49(4): 288-35.

[2]Fadlullahh Z M, Fouda MM M, Kato N,et al. Toward iintelligent mmachine-to-macchine communnications in ssmart grid[J].Communicationns Magazine,IEEE, 2011, 449(4): 60-65.

[3]简鑫, 曾孝平, 贾云健, 等. 机器类通信流量建模与过载控制[JJ]. 通信学报, 22013, 34(9): 1223-131.

[4]DemirelB, Zou Z, Solddati P, et al. MModular co-desiggn of controlleers and transmiission schedules in WirelessHHART [C]. Deccision and Conttrol and European Control Coonference (CCDC-ECC), 2011 50th IEEE CConference on. IIEEE, 2011: 59951-5958.

[5]Jaramilloo J J, Srikant RR, Ying L. Schheduling for opttimal rate alloocation in ad hhoc networks wwith heterogenneous delay constraints [J]. Seelected Areas iin Communicattions, IEEE Jouurnal on, 2011,29(5): 979-9877.

[6]Saifullahh A, Xu Y, LuC, et al. Real-time scheduling for WirelesssHART networkks[C]. Real-Timme Systems Symmposium (RTTSS), 2010 IEEEE 31st. IEEE, 22010: 150-159.

[7]陈一骄,卢泽新,孙志刚,等.可重构路由器报文转发引擎设计与实现[J].通信学报, 2012, 33(8)): 42-51.

[8]Zou Z, SSoldati P, Zhanng H, et al. Energy-efficient ddeadline-consstrained maximmum reliabilityforwarding in llossy networkss [J].WirelessCommunicatioons, IEEE Trannsactions on,2012, 11(10):3474-3483.

[9]Zou Z, Joohansson M. MMinimum-energyy packet forwarrding over lossy networks unnder deadlineand reliabilityconstraints[CC]. Modelingand Optimizattion in Mobile, Ad Hoc andd Wireless Netwworks (WiOpt),2012 10th Inteernational Syymposium on. IEEE, 2012: 2244-231.

[10]Kaelblinng L P, LittmanM L, Cassandraa A R. Planningg and acting inn partially obseervable stochasttic domains [J]. Artificial inntelligence, 19998, 101(1): 99-1134.

[11]Gershmaan A B, Sidiropoulos N D, Shaahbazpanahi S,et al. Convexoptimization-bbased beamformming: From recceive to transmmit and networkk designs [J]. IEEEE Signal Proocess, 2010, 277(3): 62-75.

Research on Packet Forwarding Strategies Based on Deadline Constraints in Wireless Multi-hop Networks

Liu Meng
(Dongguan Science and Technology School, Dongguan 523000, China)

This paper researches on the problem of real-time packet forwarding in wireless multi-hop networks with lossy and bursty links. The objective is to maximize the probability that individual packets reach their destination before a hard deadline. While the instantaneous channel statuses are not accessible, they can be estimated by observations of success and failure rate during the actual packet transmissions. The packet forwarding problem can be regarded as a partial observable Markov decision process and it can also get the optimal transmission strategy for maximizing the probability of on-time packet delivery. In addition, the approximate solution based on maximum-volume inscribed ellipsoids is obtained to reduce the complexity of implementation. The simulation results also show the effectiveness of the proposed scheme.

Wireless Multi-hop Networks; Packet Forwarding; Deadline; Markov Chains; Optimal Forwarding Policy; Maximum-volume Inscribed Ellipsoids

TP393

A

2015.02.09）

1007-757X(2015)04-0027-05

刘猛（1981-），男，邳州人，东莞理工学校，讲师，研究方向：网络安全、信息检索，东莞，523000