能量高效的协作路由算法

凌 明，张大方，张 继

（湖南大学 信息科学与工程学院，湖南 长沙410082）

0 引 言

无线传 感器网络 （wireless sensor networks，WSNs）的节点能量十分有限，且难以二次补充。如何降低或者平衡网络的能耗，成为WSNs研究的一个重要方向。大量研究表明，协作通信对于降低传输功率、提高系统容量和扩大覆盖范围具有很好的效果。把协作通信技术应用于WSNs，成为提高网络性能、降低能量开销的有效方式。

协作通信是利用无线信道的广播特性，通过共享网络中其他节点的天线，形成虚拟的天线阵列，获得性能增益。天线阵列可以减低共道干扰和多级衰落的影响，因此在一定的误码率和中断概率下，协作可以降低发射功率。通过协作能够有效解决WSNs中能耗效率问题。协作路由是联合物理层的协作通信技术和网络层的路由选择技术的跨层路由选择技术。结合WSNs的特点，设计一种低算法复杂度的能量高效的路由算法成为协作路由研究的热点。

本文提出了一种能量高效的分布式、多跳、多中继协作路由算法CWRN。算法利用无线通信信道的广播特性，形成虚拟MIMO （multiple－input multiple－output），进行协作传输。仿真实验结果表明，在保持误码率一定的情况下，新算法能够降低能量开销。

1 相关工作

文献 ［1］提出了一种基于传输速率的协作路由算法，算法的主要思想是传输速率高的节点通过转发数据包帮助传输速率低的节点传输数据。文章对于如何发现协作节点进行了详细的描述。但文章只有单个协作节点参与传输，也没有考虑到如何节省能量开销。文献 ［2］中当协作节点在经过一段等待后，仍然没有收到目的节点的确认信息，协作节点选择重发，在任何时候只有单个协作节点去重发数据包。因此，文章的目的仅仅是降低误码率，同样没有考虑节省能量开销问题。文献 ［3－5］描述的是在每一跳的发送端和接收端中，都只有单个中继节点参与协作传输。文献 ［6］提出了一种基于MAC层的分簇集中式MIMO 系统，此协议中簇的形成类似于LEACH 协议。在路由路径上，某个簇内的节点只发送数据包给下一簇的簇头节点。这种集中式的结构需要消耗大量的能量去进行簇的维护。相比之下，分布式机制下簇的维护更容易，并且不会因为单节点失效影响整体网络运行。因此，分布式机制更加适合于WSNs。

在网络层方面，文献 ［7］采用分簇机制，分析了两个簇之间进行协作时的功率消耗，认为接收端由节点簇代替单个节点可以降低传输的能耗和提高吞吐量。文献 ［8］提出一种分布式的最小功率协作路由算法：MPCR 算法。算法在保证一定吞吐量的情况下选择能量消耗最小的中继节点进行协作传输，算法考虑的是吞吐量和发送功率的关系。文献 ［9］在MPCR 算法的基础上提出了MPSDF算法，分析了发射功率同中断概率关系，推导出在一定误码率下的最小发射功率表达式。

文献 ［10］提出了一种分布式的能量高效的协作路由算法：CWR 算 法，是 一 种 基 于MISO （multiple－input single－output）实现了MIMO 的协作路由算法。算法的复杂度低，并且能够获得MIMO 系统增益。在进行中继选择时考虑了备选中继到上一跳以及备选中继到下一跳的信道状况。算法可以采用多中继进行传输，但是并没有对各跳中继节点个数进行研究。

2 算法介绍

本文提出的协作路由算法CWRN 是一种采用多输入单输出 （MISO）实现多输入多输出 （MIMO）的多跳、多中继协作路由算法。协作模型如图1所示，形成了一种虚拟MIMO 系统，并进行协作传输。协议中，协作中继采用放大转发的方式转发数据，在接收端采用最大合并比 （maximal ratio combining，MRC）技术合并信号。分簇机制已被证明能够提高系统性能和降低传输功率，本协议也采用分簇机制组织协作节点。此外，我们还假设信道状态信息（channel state information，CSI）是完全的，同时不考虑传输过程中的同步问题。

2.1 路由的两个阶段

如图1所示，整个协作路由分成两个阶段：路由阶段和中继选择阶段。路由阶段，通过AODV 协议寻找一条由源节点到目的节点的路径最短的单径路由；中继选择阶段，以单径路由上的每个节点为簇头，招募它们的邻居节点为备选中继节点，确定中继节点。AODV 协议是无线自组网按需平 面距离向 量 路 由协 议 （Ad－hoc on－demand distance vector routing，AODV），我们对AODV 协议进行了一些修改，加入了能量因素，并把链路所需的传输功率作为该链路的链路代价。我们假设簇间距离要远大于簇内节点的距离，因而，簇头节点能够招募到其附近的邻居节点作为中继节点。

图1 协作模型

图2为中继选择阶段的过程图。在路由过程中，中继选择阶段分为5个步骤。如图2所示的场景中，需要确定簇头节点5所在的第k 跳簇的中继节点。中继选择的第一步：发送端簇头节点2发送一个请求招募包 （request－to－recruit packet）给接收端簇头节点5，包括发送端簇头ID、接收端簇头ID、sink节点ID、NAV field；第二步：簇头节点5广播招募包 （recruit packet）给它的邻居节点，所有收到招募包的邻居定义为候选中继阶段，招募包包括发送端簇头ID、接收端簇头ID、最大的应答时间T；第三步：所有的候选中继计算链路代价并发送同意包 （grant packet）给簇头节点，链路代价包括两个部分：发送端簇内节点到候选中继链路代价的算术平均、以及候选中继到接收端簇内节点到候选中继链路代价的算术平均。例如，节点4需计算链路 ［1，4］、［2，4］、 ［3，4］和 ［4，8］的能量开销，即 （C1，4＋C2，4＋C3，4）／3＋C4，8。类 似 的，节 点6 计算链路 ［1，6］、 ［2，6］、 ［3，6］和 ［6，8］即（C1，6＋C2，6＋C3，6）／3＋C6，8。各节点间链路能量开销情况在路由阶段获取；第四步：簇头节点根据簇间物理位置信息和链路代价确定中继节点个数mk并选定中继节点ID，发送清除包 （clear packet）给候选中继及前一跳簇头节点。选定链路代价最小的前mk个为k 跳的中继节点，同意的候选中继节点数小于mk时则全部同意的候选中继节点为k 跳的中继节点；清除包包括确定中继节点个数mk、选定中继节点ID 以及更新的NAV 值；第五步：发送端簇头发送确认包 （confirm packet）给它的簇内节点，包含下一跳接收端的节点ID、发送功率Pt、同步时间。传输功率为发送功率Pt除以发送端节点个数（mk＋1），mk为第k 跳中继节点个数。

2.2 链路代价计算

图2 中继选择阶段

2.3 中继节点个数的确定

通过大量的实验，我们发现簇间距离比较小时，减少中继节点个数总能量更有效，当距离变大时，增加中继节点个数总能量更有效。产生这种现象的主要原因是：簇间距离大时，中继信道同时出现衰落的概率大，增加中继个数，能提高接收信号的信噪比，这时多个中继参与协作的性能更好；而距离小时，如果采用多个中继协作，信道间相互干扰等原因会导致频谱利用率低，减少中继节点个数反而性能更好。

2.4 模型分析

3 算法分析

根据以上公式分析包错误率Pf：假设Pt＝1 W ，γ ＝3，跳数i＝10，Pη＝10－10w，包的长度为1000bits，当n＝2，Pf＝0.0095；当n＝3，Pf＝0.0028；当n＝5，Pf＝0.0011；而当n＝7时，Pf＝0.0017。计算结果表明中继节点数并不是越多越好，存在一个优化值。

4 仿真实验及结果

在本节，我们通过同CWR 算法相比较，对NCWR 算法的能耗情况进行仿真实验。实验场景是在一个400×400的空间内，随机散布50 个节点，节点的通讯半径是150米，邻居半径是50米，各节点的初始能量为0.5，数据包长度为1KB，γ＝3。通过两组实验分析新算法的性能。

图3为能耗对比图，横坐标代表数据量，纵坐标代表剩余能量，此处为所有节点的平均剩余能量。数据表明，在误码率一定的情况下，随着传输数据量的增加，NCWR相比CWR 算法在能耗方面节省6.41%以上。如图3所示，在原算法m＝1时，能耗节省32.15%，当m＝2时，节省14.71%，当m＝3时，节省8.74%，当m＞＝4时，节省6.41%。m＞＝4时，在此节点密度下，簇头没有更多的邻居节点可以招募，参与传输的节点不变。可以看出新算法能耗比CWR 算法能耗有所减低，主要原因是新算法参与协作的中继节点数随着簇间距离的增加而增多，较多的中继节点数在距离增加的情况下能够获得增大的分集增益，从而减少传输端能量开销。

图3 能耗对比

图4为中继节点个数相同时两种算法的能耗情况，当CWR算法中m＝2时，选择两种算法的参与协作的中继个数相同的链路进行实验。如图4，此种情况下，NCWR 能耗节省15.46%。原因是新中继选择要更优，此外通过优化中继节点的分配也可以节省能耗。

图4 中继个数相同时能耗对比

5 结束语

本文提出了一种能量高效的协作路由算法，通过MISO实现了MIMO，算法的复杂度较低，但可以获得较高的协作分集增益。对中继选择时中继选择方式和中继节点个数进行了研究，提出一种基于簇间物理距离的中继节点个数确定算法，在相对簇间距离增大时，选择较多的中继节点参与协作传输，相反，则选择较少的中继节点个数。实验结果表明新算法在能耗方面有所改善。本算法性能的提高在节点均匀分布的网络并不明显。

下一步工作是对多跳、多中继网络场景下最小功率进行研究，设计一种适合节点均匀分布的算法，并使得能耗进一步降低。

［1］Korakis T，Narayanan S，Bagri A，et al.Implementing a cooperative MAC protocol for wireless LANs［C］／／IEEE International Conference on Communications，2006：4805－4810.

［2］Khandani，Amir Ehsan.Cooperative routing in static wireless networks［J］.IEEE Transactions on Communications，2007，55 （11）：2185－2192.

［3］Hunter Todd E，Aria Nosratinia.Diversity through coded cooperation［J］.IEEE Transactions on Wireless Communications，2006，5（2）：283－289.

［4］Ibrahim，Ahmed S.SPC12－5：Relay selection in multi－node cooperative communications：when to cooperate and whom to cooperate with［C］／／Global Telecommunications Conference，2006.

［5］Dehghan M，Ghaderi M，Goeckel D L.On the performance of cooperative routing in wireless networks ［C］／／IEEE Conference on Computer Communications Workshops，2010：1－5.

［6］Yuan Y，Chen M，Kwon T.A novel cluster－based cooperative MIMO scheme for multi－hop wireless sensor networks ［J］.EURASIP Journal on Wireless Communications and Networking，2006 （2）：38－38.

［7］Vardhe K，Reynolds D，Woerner B D.Joint power allocation and relay selection for multiuser cooperative communication［J］.IEEE Transactions on Wireless Communications，2010，9（4）：1255－1260.

［8］Ibrahim A，Han Z，Liu K J R.Distributed energy－efficient cooperative routing in wireless networks［J］.IEEE Transactions on Wireless Communications，2008，7 （10）：3930－3941.

［9］Sheng Z，Ding Z，Leung K K.Distributed and power efficient routing in wireless cooperative networks ［C］／／IEEE International Conference on Communications，2009：1－5.

［10］Elhawary M，Haas Z J.Energy－efficient protocol for cooperative networks［J］.IEEE／ACM Transactions on Networking，2011，19 （2）：561－574.

［11］Chen G，Alnatouh O，Ge L，et al.Performance analysis of four relays selection scheme for cooperative networks ［C］／／11th International Conference on Information Science，Signal Processing and their Applications，2012：137－140.

［12］Jiang H，Zhang S，Zhou W.Energy－efficient distributed relay selection based on statistical channel state information ［M］.Wireless Internet.Berlin：Springer Berlin Heidelberg，2012：388－399.