WSN中的自适应机会路由

聂 骕

(上海海事大学 商船学院，中国 上海 201306)

0 引言

无线传感网是由许多低功耗的传感器节点组成的，它们通常具有感知、计算、通信能力。现阶段的研究多数是静态的无线传感网，如森林防火、建筑监控、地标检测等等，这样的应用环境中，网络比较稳定，传感器节点基本没有拓扑变化，因此便于运用，且网络效率较高。而在有的应用领域，如海上搜救等重要领域，应用环境比较恶劣，常常由于海上各种客观因素，包括风压、海流、大风大浪的影响，网络信道质量通常较差，节点之间并不是总存在一条可达路径，因此传统的路由并不适合于类似海上的恶劣环境。

因此，本文针对近年，对于无线传感网（WSN）的研究现在正不断的增长，在Ad hoc 无线网中，资源限制一直是重要而又难以解决的问题。机会路由的提出，有效的改善了这些问题。机会路由通过充分利用无线信道的广播特性，可以大大提高无线多跳网络的性能。因此，自从机会路由被提出后，也成为了各个研究机构的研究热点。现在的一些路由方案，都是采用ETX 当路由判据，ETX 的获取需要周期性地发送探测包，路由的开销很大。

最具有代表性的机会路由协议有ExOR[1]，SAOR[3]。但是它们都有很大的改进空间，如ExOR 存在数据包传输效率不高，可扩展性不强等问题。传统的路由模式是：在端到端数据包传送过程中，先建立一条端到端的节点序列，然后在每次分组转发时，已经下一跳的节点，开始执行链路层数据的转发。因此一旦传送过程有分组丢失或者错误，那么就要重新启动链路层开始从头再来。所以可以看出，在链路质量和稳定性较差的环境下，频繁的链路层数据重传将消耗大量的带宽资源。因此，尽管确定性路由方式逻辑简单，但未能充分考虑无线信道的广播特性、时变特性和干扰不规则性。无线信道的广播特性使得一次分组转发可能被多个节点收到，且接收概率各不相同；无线链路的时变特性导致网络中链路的状态随时间而改变。路由协议设计过程中如果缺乏对信道广播和丢失特性的充分考虑，必将导致大量网络资源无谓浪费，这将严重影响无线多跳网络的吞吐量和提供服务质量的能力。

1 机会主义路由工作机理

机会主义路由(Opportunistic outing)是一种后择路由，节点在转发包时不以源-目标节点间直接可达路径为基础，而是将报文广播出去后，再利用转发候选集中的最佳节点来转发报文。充分利用无线信道的广播特性，机会性的选择报文能到达的最佳节点转发，尽可能地克服动态拓扑、链路信道变化频繁等影响，从而有效提高无线网络性能。不先确定下一跳节点，这样可以选择最佳的节点来转发数据包。假设源节点要广播数据包，那么监听到这个数据包的邻居节点组成一个转发节点列表，每次传输都以最佳节点（如离目标节点最近，或开销最小）来转发报文。

路由是在网络数据通信系统的一个重要的要求。有路由协议所需要的三个主要组成部分：一个目的地的规范，路由目标和策略路由。大多数路由协议是基于一个固定的目标规范，路由目标和路由策略往往遵循分层计划。有两种通用的有线网络和无线网络中的最短路径（或最低的成本）的路由范例通常被采用，一是在一个单一的任何源-目的对之间的最短路径的计算。这被称为隐式应答路由。在无线传感器网络中，要考虑到具有挑战性的环境中的资源约束和频繁的干扰和节点故障，路由无线传感器网络必须精心设计和优化-理想与本地适应能力的数据传输速率和网络条件的变化。此外，一个典型的无线传感器网络中的通信模式，要包括传感器和接收器节点布置。

已经有一些关于OR 的改进的变种，采取机会主义传输的概念了利用无线网络的时空多样性。在一般情况下都是采用以下两种常见的方法：

i)随机无限制的CR

ii)先决和限制的CR

第一种类型中，能源是不是一个主要的问题，而第二种类型是以确保潜在的中继节点参与形成源目标路径在能源效率方面具有最大的潜在回报为目的。

第一个可供选择的潜在的中继节点只需要一个最小的初始化时间，第二个版本是需要额外的初始化时间来确定的，可用于对每次发送的每个中继节点组。由于其在无线传感器网络中的潜在用途，这个版本将本文中详细探讨。

OR 协议程序的重要方面之一是每个节点的潜在中继之间的协调。下面将会讲到自适应机会路由的具体描述。

2 自适应机会路由的具体描述

自适应机会路由其性能取决于几个重要因素：候选转发节点的选择；候选节点的优先级；候选节点之间的协调。

2.1 候选转发节点的选择

由于无线网络的性质，每次传输，在默认情况下，都被当做是一个广播操作。传输范围内的所有节点可以监听消息，并实现了不同的数据包的接收率。此外，最近的研究表明，除了有被“连接”和“断开”地区，许多环节都在一个区域内被称为“过渡区”，实际上，它们可能具有最高的能源效率。然而，为了确保每个传输的能量，可靠性和准确性方面是有效的，必须设计挑选出来一个适当的度量。这个度量必须确保只有相关的节点都参与或考虑在每次传输。理想的情况下，该指标应共同考虑几个因素，如数据包接收率，距离，数据包转发时间和跳步。

选择过程的主要目的是确定候选中继节点的集合，给出一个最优的数据包转发效率。分析涉及的候选节点在设置平衡时需要仔细分析。有许多候选集合中的中继，往往导致在减少成本的转发。然而，一些邻居不取得进展如预期前往目的地。此外，在一个密集的网络，由于冗余传输，越来越多的候选节点有可能增加开销，以及导致能源利用效率低下。

2.2 候选节点的优先级设置

在决定中了候选中继（CRS）的节点的数量之后，下一个问题是根据优先顺序排列这些节点。这个排名为每个传输的最大化或最小化提供一个是很重要的客观标准，如是寿命，延迟和吞吐量。同样重要的是被选择的节点的CRS，要提高可靠性的每个传输之间的协调。理想情况下，将被用于计算每个候选的优先级度量的属性必须反映了链路，距离，和能量水平等条件。

这里，我们设置一个无序的节点集V，v∈（1，n）的整数，v 为节点，假设这些节点有有限的队列缓冲器，此外知道他们自己的位置，以及邻居节点的位置以及目标节点的信息。在OR 里，每个节点v 将选择候选节点并且列出优先级来转发它的数据包到目的节点。因此，这些节点应该以要是监听到源节点转发数据包信息的节点，二还得是根据链路信息质量，距目的节点的距离较近并且能够联系到目标节点的节点。（即图1 中的重叠阴影区所包含的节点）

图1

为了考虑将节点的失败考虑进去，我们要设定一个延迟时间T，如果第一个最佳候选节点没有转发成功，在T 时间之后，最佳候选节点列表里的第二个节点进行转发，如此直到目的节点收到数据包。所以总体上说，一个节点的优先级越高，它等待转发数据包的时间越短。当节点等待轮到它转发数据包时，如果节点收到一个更高优先级节点告诉它数据包已经被发送的消息时，它将丢弃那个数据包。这就是隐式应答程序，它对消除数据包被多重转发有重要的作用，同时也减少冲突和中断。隐式应答程序机制的主要优势是不需要一个精确的数据包应答，因此也节省了能量。

2.3 候选节点的协调

由于需要处理中的多个节点的CRS 的潜在需要，在这些节点之间的协调非常重要，基本上在MAC 层进行协调。协调这些节点的主要目的是为了防止重复的数据包转发到目的地，也承认包接收成功的可靠性的目的。这些节点的协调途径之一涉及附加为每个CRS 候选的优先级信息，然后发送它的开销。这样，在CRS 中的每个节点将了解的其他节点的优先级。根据此信息，候选节点的调度，可以进行避免碰撞和减少交通堵塞的目的，一个隐含的确认数据包可以被发送到发送方。整体实施的协调机制也较难，因为应答程序也受无线网络环境的影响。一个强大的机会路由机制是以确保采用高增益无线传感器网络受青睐的。

3 总结

本文提出了一个关于改进机会路由主义的建议，是根据每个节点的不同情况做出自适应反应，尽量让数据包能成功传输到目的节点。它利用现有的隐式应答程序来决定节点与其他所有节点之间的关系，这个加强策略对于端到端延迟，数据包传输率及能效都会有比较好的效果。当然只是初步建议，如未来有具体仿真是更好。

［1］S.Biswas and R.Morris.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks[C]//SIGCOMM.,2005.

［2］H.Dubois-Ferriere,M.Grossglauser,and M.Vetterli.Leastcost Opportunistic Routing [C]//45th Proceedings of the Allerton Conference on Communication,Control and Computing,2007.

［3］Bejerano Y,Breitbart Y,Garofalakis M,et al.Physical Topology Discovery for Large Multi-subnet Networks [C]//Proceedings of IEEE INFOCOM’03.New York,USA:IEEE Press,2003:342-352.

［4］梁绍芳，武穆清，甄岩.适用于多跳无线网络的机会路由机制[J].计算机工程，2010，19(36)：137-141.