基于Markov预测模型的ETX路由判据研究

苏浩明，黄 晞，施文灶，刘一粟

(1.福建师范大学 光电与信息工程学院，福建 福州 350007；2.福建师范大学 地理科学学院，福建 福州 350007)

0 引 言

无线Mesh网络结合了ad hoc网络和传统无线网络的优点。其核心指导思想是让网络中的每个移动或固定节点都可以发送和接收信号，节点间的通信不再需要接入点转接。通过多跳网络的构造，数据可以通过相邻节点间的转发传送到目的地，减小了流量拥塞的可能性，大大提高了网络整体性能[1-2]。

路由判据用来计算源节点到目的节点的开销最小的路径，需确保路由稳定、网络性能良好、算法明确、无路由环路。众多适合于无线Mesh网络的路由判据中，ETX(expected transmission count，期望传输次数)通过某个链路从源节点到目的节点在过去一段时间内发送一个数据包的平均传输次数，来预测未来发送一个数据包所需要的传输次数。但这样的路由判据只能反映历史时间内网络性能的情况，没有考虑节点移动引起的网络拓扑和性能的变化，因此对于网络节点移动频繁的场景，该路由判据有很大的局限性[3-4]。因此，文中提出一种改进的基于Markov数学模型的ETX路由判据，通过节点过去一段时间的位置，预测节点未来的位置，判断在下一时刻源节点和目的节点是否在彼此的通信范围内，以确定ETX路由判据是否失效，从而选择出更加合适的路由。

1 ETX判据及其改进

1.1 传统ETX判据

ETX路由判据的思路是根据历史时间内成功传输到目的节点所需要的平均发送次数来预测未来一段时间成功传输到目的节点所需要的发送次数。这一路由判据一般应用于无线Mesh网络[4]。无线链路的ETX是指无线链路上成功传输一个分组时所需的平均预计传输次数[5]。ETX中，每个节点定期广播一个固定长度的专用链路探测包，这个数据包包含最后一段探测时间内从每个相邻节点接收到的探测分组的数据。

每个节点通过相邻节点转发或反向发送的专用链路探测包，可以计算出成功递交率df和dr[6]，然后就可以得到期望传输次数了，如下所示：

ETX=1/df×dr

(1)

这种传统ETX路由判据没有考虑节点的运动带来的拓扑变化，无法判断下一时刻节点是否在彼此的通信范围内，不能据此做出相应的路由调整，且对拓扑变化的反应速度太慢，存在潜在的不稳定性，难以满足节点地理位置和网络拓扑变化频繁的网络系统高速率传输、高吞吐量和快速收敛的需求。

1.2 改进的ETX判据

改进传统ETX路由判据的问题，不仅需要预测未来节点之间的平均传输次数，还需要预测节点未来的运动轨迹，据此判断下一时刻节点是否在彼此的通信范围内，是否需要调整路由。通过在直角坐标系中定位网络系统中各节点的位置，获取节点的横纵坐标，并以时间为自变量，将历史时间内节点的坐标-时间的关系带入Markov数学预测模型，来预测节点下一时刻的坐标，从而获取节点下一时刻的位置。根据对节点下一时刻位置的预测，如果下一时刻节点还在彼此的通信范围内，则原ETX路由判据不需要修改，如果不在彼此的通信范围内，那么这条链路判定失效[7-9]，选择ETX次之的路由并同样判断下一时刻是否在彼此的通信范围内，以此类推直至找出最优路由。

2 改进ETX判据的实现

2.1 在专用链路探测包中加入地理位置信息

传统的ETX路由判据的探测包中有探测包生成的时间、历史时间内接收到的相邻节点的IP信息及其发出的探测包的数目[10]。改进ETX判据，需在探测包中加入节点地理位置的信息，预测节点下一时刻的位置。文中的路由判据在DSR路由协议内实现，其探测包的格式可以改进为：

struct link_probe{

float now_;

……

double position_x;//①

double position_y;//②

double position_z//③

};

其中，①、②、③三句为探测包中添加的信息，position_x、position_y、position_z为节点的地理位置在三维直角坐标系中的三维坐标。

2.2 利用Markov模型预测节点下一时刻地理位置

Markov链是一种离散时间随机过程，可以根据当前位置，预测下一时刻位置[11]。Markov模型可以很好地预测基于时间序列的各种参数，是一种消耗代价小、准确率较高的地理位置预测方法。其基本思想为：Xn=i表示在n时刻对象处于状态i，对于每一个状态i，存在一个固定概率Pij≥0，使其下一时刻处于状态j[12-13]。其公式为：

Pr(Xn+1=j|Xn=i,Xn-1=in-1,…,X1=i1,

X0=i0)=Pij

(2)

对于上述公式，可以解释为：任何下一时刻的状态Xn+1独立于过去时刻的状态Xn-1，…，X1，X0，只取决于上一时刻状态Xn[12-13]，即

Pr(Xn+1=j|Xn=i,Xn-1=in-1,…,X1=i1,

X0=i0)=Pr(Xn+1=j|Xn=i)=Pij

(3)

建立转移概率矩阵：

(4)

矩阵的行元素表示历史位置(状态)，列元素表示下一个位置。矩阵元素表示在行元素代表的历史位置(状态)的条件下的下一个位置到达列元素代表的位置的概率。

(5)

在进行移动预测时，根据轨迹定位到转移概率矩阵中的相应行，该行中最大概率值对应的列所代表的位置为预测结果：

Xp=argmax{p{Xn+1|C}}

(6)

其中，Xp为预测结果；C为当前位置。

对于ETX路由判据，由于其周期性广播探测包，时间序列为离散的，故文中涉及到的对于地理位置的预测可以使用该方法。根据节点在t-1时刻和t时刻的地理位置信息，利用Markov模型分别预测出t+1时刻节点的位置，再利用最小均方误差预测，修正计算出节点在t+1的地理位置作为最终预测结果。

2.3 判断下一时刻节点是否在各自通信范围内

利用上述方法分别计算出相邻节点i和j各自在下一时刻的地理位置，并据此计算出两个相邻节点下一时刻的距离：

d=

(7)

其中，xi、yi分别指两个相邻节点[14-15]。

3 测试与仿真

3.1 仿真环境

基于Ubuntu操作系统的NS-2仿真平台进行仿真模拟实验，实验使用DSR路由协议。NS-2是一种面向对象的网络模拟器，使用OTCL和C++两种语言，可用于模拟各种不同的通信网络和通信协议[16-17]。DSR(dynamic source routing，动态源路由)协议是一种按需更新反应式路由协议[18]。

实验设计20个节点随机分布在一个800 m×800 m的区域内，每个节点的通信范围均为250 m，信道容量2 Mbit/s，如图1所示。

图1 仿真环境

仿真流程如图2所示。

图2 仿真流程

3.2 仿真结果

首先固定节点移动速度，改变业务速率，分别仿真分析加入改进的ETX路由判据节点的吞吐量、丢包率和时延的变化情况。

固定节点的移动速度为30 m/s，分别改变节点的业务速率进行仿真实验。每个节点的业务速率从5 kbps增加到30 kbps。随着节点业务速率的不断提升，DSR和加入改进ETX路由协议的吞吐量均有提升，且加入改进ETX路由协议的提升更加明显。当节点速率为5 kbps和10 kbps时，改进ETX路由协议和DSR路由协议的吞吐量大致相同，但是当节点业务速率进一步提升时，DSR路由协议的吞吐量最终维持在280 kbps左右，而改进ETX路由协议可达到390 kbps，改进ETX路由协议的吞吐量提高了约40%。仿真结果如图3所示。

图3 吞吐量随业务速率的变化

从丢包率来看，随着业务速率的不断提升，相应的DSR路由协议和改进的ETX路由协议的丢包率均明显提升，但改进ETX路由协议的丢包率均小于DSR路由协议。当节点业务速率为30 kbps时，丢包率降低约30%。从时延来看，改进的ETX路由协议对于业务时延的保障显著优于DSR路由算法，业务速率在20 kbps以内，时延基本保持不变，业务速率大于20 kbps，其时延才会提高，但仍然明显低于DSR路由协议，当节点业务速率为30 kbps时，平均时延降低了约60%，如图4和图5所示。

图4 丢包率随业务速率的变化

图5 时延随业务速率的变化

再固定节点的业务速率，改变移动速度，分别仿真分析加入改进的ETX路由判据前后节点的吞吐量、丢包率和时延的变化情况。

固定节点的业务速率为25 kbps，分别改变节点的移动速度进行仿真实验。每个节点的移动速度从5 m/s增加到30 m/s。随着节点移动速度的不断提升，DSR和加入改进ETX路由协议的吞吐量显著降低，因为随着节点的移动网络拓扑发生变化，DSR需要不断发送探测包更新路由表。但加入改进ETX路由协议的降低幅度较小。当节点速率为5 kbps和10 kbps时，改进ETX路由协议和DSR路由协议的吞吐量大致相同，但是当节点业务速率进一步提升时，DSR路由协议的吞吐量最终维持在280 kbps左右，而改进的ETX路由协议则可以达到390 kbps，改进ETX路由协议的吞吐量提高了30%，数据变化趋势与固定节点移动速度、改变业务速率时类似。

从丢包率来看，节点移动速度的不断提升，相应的DSR路由协议和改进的ETX路由协议的丢包率均有增加，但是ETX路由协议的丢包率始终小于DSR路由协议，当节点业务速率为30 m/s时，丢包率降低约30%。从时延来看，从两种路由协议在平均时延方面的对比可以看出，当节点业务速率不变、移动速度增加时，ETX路由协议的时延始终保持在DSR路由协议时延的1/3以下，节点移动速度为30 m/s时，此时延比例降低为1/5；改进ETX路由协议时延保持了良好的稳定性，节点移动速度由5 m/s增加到30 m/s时，平均时延比未改进时降低约80%，较为明显。两组的数据变化趋势也均与固定节点移动速度，改变业务速率时类似。再次说明ETX路由协议对于业务的时延具有良好的保障。

综上，在加入改进ETX路由协议后，当节点业务速率不变时，随着节点运动速度的增加，其吞吐量比没有加入改进ETX的DSR路由协议有所提高，时延和丢包率有所降低；当节点的运动速度不变时，随着节点业务速率的增加，其吞吐量也比没有加入改进ETX的DSR路由协议有所提高，时延和丢包率有所降低。在节点运动频率较高的网络系统中，改进的ETX路由判据明显提高了网络整体性能，且随着节点运动速度和业务速率的提高，这种网络性能的提高越来越明显。

4 结束语

传统ETX路由判据由于缺乏对节点运动引起的网络变化的预测，存在路由选择不尽合理、影响网络整体性能的问题。在传统ETX路由判据的基础上，文中提出一种基于Markov地理位置预测模型的ETX路由判据，预测节点下一时刻的地理位置，确定原路由是否失效，从而优化路由的选择，提高网络整体性能。在NS-2中的仿真结果表明，在节点运动频率较高时，改进的路由判据明显提高了网络的整体性能。