无线传感器网络中基于尺度的协同中继跨层QoS路由算法

徐 楠，孙亚民，于继明，王 华

(1.南京理工大学计算机科学与技术学院，南京 210094;2.浙江工业大学计算机科学与技术学院，杭州 310014;3.山东大学计算机科学与技术学院，济南 250023)

无线传感器网络中基于尺度的协同中继跨层QoS路由算法

徐 楠1，孙亚民1，于继明2，王 华3

(1.南京理工大学计算机科学与技术学院，南京 210094;2.浙江工业大学计算机科学与技术学院，杭州 310014;3.山东大学计算机科学与技术学院，济南 250023)

提出了一种基于尺度的协同中继自主转发跨层QoS路由算法(MCRICQR)。节点根据能量、信道、拥塞以及与汇点的距离等综合因素形成一个选择度量，度量最大的节点根据自己所处状态自主选择直接转发、中继转发以及跃进转发数据包。仿真结果表明，该算法能根据网络状况及时转发数据，提高网络可靠性，对网络负载进行均衡，提高网络吞吐量和能量效率，从而延长网络寿命，保障了无线传感器网络的QoS需求。

服务质量;跨层设计;协同中继;自主转发;无线传感器网络

1 前言

无线传感器网络(wireless sensor network，WSN)是一种无基础设施、多跳、自组织的网络，网络中的节点具有感知、收集、聚合、处理、转发数据的功能，通过无线信道进行通信，可以广泛地应用在军事、环境、健康、家庭、空间探索、灾难拯救和其他商业领域［1］。

无线介质的广播特性允许多个节点接收和处理同一个传输的信号［2］，协同中继就是利用这一特性，使节点协同通信，成功将信息发送到汇点。与直接传输和传统的经典中继相比，它能明显降低获得一定的中断概率所需要的信噪比(SNR)。由于无线链路造成的独特问题、在无线链路上机会通信的可能性以及无线介质所提供的通信模式，激发人们进行跨层设计的尝试。通过同时对网络的多个层次进行优化控制，跨层设计可以大幅度提高网络容量，减少干扰和功率消耗［3］。

2 系统模型

WSN节点可以用一个无向图G(V，E)来表示。V表示节点集合，E表示边的集合。节点u和v间存在边(u，v)∈E，意味着u和v间存在一条可以互相通信的无线链路。

2.1 基本定义

定义1 虚拟自主转发节点是这样的节点集合U

定义2 下一跳可行自主转发虚拟节点集合J。当一个节点i有DATA包要发送时，i就广播一个RTS请求，其邻居就会收到该广播包，那些比节点i距离汇点更近，并且符合公式(1)的节点j的集合就形成下一跳可行自主转发虚拟节点集合J，节点j会向节点i发送CTS。

定义3 虚拟中继可行节点集合R。假定节点的i下一跳转发节点是j，虚拟中继可行转发节点集是这样的节点集合:节点r在下一跳转发节点j的传输范围之内，并收到来自节点i的一个RTS及一个DATA包，将该DATA包存储，当下一跳节点j不能解码数据包时，节点j会发一个“重新传输请求”(RREQ)控制包给节点i，偷听到RREQ控制包的节点r的集合形成一个虚拟可行中继节点集R。

定义4 虚拟可行跃进节点L。虚拟可行跃进节点属于这样的节点集合:偷听到一个中继节点传输的DATA包的节点，该节点从没有收到这个DATA包的RTS，并能对所收到的DATA包进行正确解码，比下一跳节点距离汇点更近的节点I所形成的节点集合L。

2.2 链路和网络假设

网络中所有节点具有自己的位置信息以及汇点sink的位置信息;除sink节点外，每个节点在协同将数据包从源传输到汇点的过程中，可以作为下一跳的转发节点NHF(next_hop forwarding node)、中继节点RFN(relay forwarding node)或作为跃进节点LPF(leapfrogging node)，在这里，我们称这些符合条件的节点形成一个虚拟可行转发节点集合。下一跳节点与传统的方法相似，将数据包逐跳转发。为了确保虚拟节点集合中最适合的节点选择来转发数据，符合条件的虚拟节点集合中的节点竞争作为NHF、RFN、LPF节点。节点的选择和节点的角色分配过程是基于尺度来进行的。

假设有|V|个节点均匀地分布在整个无线传感器网络中。每个节点都安装了一幅全向天线，这样每个节点都可以从其他节点接收到信息，并且网络中的所有节点都是工作在半双工模式，即不能同时接收和发送。同时假设每个节点的背景噪声是方差为σ2的高斯噪声。每个节点接收采用最大比值合并和解码中继协议，即当节点正确接收信息后，才将信息转发到下一跳节点，这样每一条的信息传输都是可靠传输，可以避免错误信息被传递。MAC层协议利用带RTS/CTS的CSMA协议。

信道模型。瑞利平坦衰落模型［4］:任何两个距离为d的传感器节点之间传输数据包输入输出关系建模:

式(2)中，α是无线信道的路径损失指数，2≤α≤6;r［t］和 s［t］分别是复合的接收信号和发射信号，g［t］是描述衰落的信道增益，g［t］～ CN(0，1)，方差被归一化为1;w［t］是均值为零的复合加性白高斯过程，波谱功率密度为 N0，w［t］～ CN(0，N0)。

式(3)中，ε0是初始能量;si是在时间i时无线收发器的状态;εs是在状态s的能量消耗。传感器节点的无线收发器状态可以是传输、发送、空闲。

3 MCRICQR算法

无线传感器网络中基于尺度的协同中继自主转发跨层QoS路由算法(metric－based cooperative relay initiative forwarding cross－ layer qos routing，MCRICQR)，与以前所提出的QoS路由算法最大的不同是:下一跳转发节点的选择由其通信范围内节点所形成的虚拟可行转发节点集合通过竞争决定，每个节点不用存储邻居节点的信息。即每个节点i根据自己当前的能量、信道状况、拥塞情况(由和来共同确定)以及与汇点的距离来决定自己所扮演的角色，节点的角色可以是NHF、RFN、LPF，然后节点自主转发数据。这样，每个节点就不需要浪费宝贵的存储空间来存储邻居节点信息。由于竞争是基于定时器时间的，可以减少信道争用，提高信道利用率。此外，节点不用为维护路由等进行额外的能量开销。

当节点i有数据包DATA要发送时，它首先广播一个RTS控制信息包，该包包含的内容有节点i的位置、DATA包标识符以及响应CTS的持续时间。RTS包可以让收到该包的节点用来作为链路质量指示器(RSSI)，计算瞬时信道增益 gi，j［t］，所有收到节点i的RTS包的节点根据公式(1)，同时满足di，sink＜ dj，sink形成一个下一跳虚拟可行转发节点集合J，集合J中的每个节点j根据公式(4)来计算尺度，根据公式(5)，选出NHF节点。

式(4)中，a，b，c为权重系数，一般设为常数。在t时刻，最佳下一跳转发节点NHF为:

下一跳虚拟可行转发集合中的每个节点j，计算尺度后，设置一个定时器的等待时间，该定时器与mj［t］成反比，定时器结束时，发送 CTS包响应该RTS包。当节点在定时器超时前听到其他节点发送的CTS对同一个RTS响应，则它放弃竞争。这种竞争基于尺度，可以提高无线链路的利用率。节点i将数据转发给赢得竞争的节点NHF。节点i忽略首次CTS到达后的所有针对该DATA的CTS包，其目的是为了避开隐藏终端的影响。

节点i收到节点NHF发来的 CTS后，就将DATA包发送给下一跳转发节点NHF。如果NHF能够成功地将DATA包接收并解码的话，则NHF就向节点i发送一个ACK控制信息包，该控制信息包包括DATA包标识符等相关信息。由此可知，上一跳和下一跳节点间是基于RTS/CTS的交换。

如果节点NHF不能正确地解码DATA包，则节点NHF就向节点i发出一个重新请求发送RREQ(该控制包也可以作为判断NHF有无中继节点的依据，当RREQ≥2时，存在中继节点)，RREQ控制包携带的内容有:DATA包的标识符，下一跳节点的地理位置信息等。节点i收到RREQ包之后，就为该重传包设置RREQ定时器，其值为NHF定时器值大小。当虚拟中继可行集合R中的每个节点偷听到RREQ后，计算瞬时信道增益，并根据计算尺度选择公式(6)，竞争最佳中继节点。根据公式(7)，可以找到RFN节点。虚拟可行中继节点集合R中的每个节点设置一个计时器，该计时器与mr［t］成反比，定时器最先到期的节点就是RFN，RFN就向节点NHF发送DATA包。其他中继节点听到有DATA在传送给NHF就放弃竞争。节点NHF成功收到DATA包后，就向节点i发送一个ACK控制包，节点i收到该ACK包后，就取消 RREQ定时器。节点NHF扮演节点i的角色转发数据包。如果虚拟可行中继节点集合为空，则上一跳节点i在设置的定时器时间过期时重传该DATA包。

在t时刻，最佳中继节点RFN为:

当节点RFN向节点NHF发送DATA包时，RFN的通信范围内的节点也会偷听到该DATA包。此时，若NHF节点还不能正确地接收该DATA包，NHF就会向节点i再次重新发出RREQ请求(此时RREQ=2，节点i就可以判断有中继节点存在，否则，在第一次RREQ到期时，节点i就会向节点NHF重传DATA包)，RFN的通信范围内的距离比NHF更接近汇点的节点就形成跃进节点集合L，集合中的每个节点l根据公式(8)来计算自己的度量，根据公式(9)，可以获得跃进节点LPF节点。然后节点l设置一个定时器，该定时器的值与ml［t］成反比，定时器最先结束的节点就发送ACK控制包到节点RFN，此时，节点NHF也会收到该 ACK控制信息包，节点NHF就会停止转发处理该DATA包。此时，LPF就扮演节点i的角色，来转发数据包给其下一跳节点。

在t时刻，最佳跃进节点LPF为:

MCRICQR算法伪代码:

跃进节点LPF向中继节点RFN发送ACK包，从而阻止节点NHF处的数据包转发过程;节点LPF再扮演节点i的角色;

4 仿真结果和分析

通过仿真实验对所提出的跨层设计方法进行算法性能评估，下面依次给出实验环境、实验设计、实验结果以及分析。

4.1 实验环境

OMNET++［5］是一种面向对象的模块化离散事件驱动的开源仿真器。在OMNET++环境下使用C++和NED实现了该算法，实验设备是一台运行 Windows XP SP2，具有 P42.8G Hz的 CPU，512M DDR内存的PC。实验中，假设100个传感器节点均匀地部署在500 m×500 m的监测区域内，sink节点被部署在(0，0)位置，节点的传输半径设为100 m。仿真过程中取权重系数a=b=c=1，表明能量和距离、信噪比以及剩余存储空间在仿真过程中认为它们按照相同权重来考虑。

4.2 实验设计与性能分析

为了使仿真结果比较具有可信性，实验设计时仿真的相关参数与文献［6］中一致。QoS routing［6］路由基于节点知道自己的地理位置，使用802.11CSMA协议。实验中，能量节点的减少与文献［6］中一致，即包接收和包发送的所消耗能量比为1.05∶1.4。数据包载荷的大小设为512 bytes，数据包在源节点的生成速率为 0.5、1、1.5、2 包/s。每个仿真运行500 s，在仿真期间，网络不断裂。在仿真开始，所有的节点能量为500单位。最后取平均值进行比较。

在图1中，MCRICQR比QoS routing平均时延低的原因在于，前者基于尺度选出最适的节点来转发数据包;当有中继节点存在时，不需要上一跳节点直接重传数据包。图2中，由于MCRICQR在进行选择转发节点的时候，考虑了节点的能量效用均衡，以及节点负载均衡的原因，获得较长的网络生存时间。QoS routing方法中，没有考虑中间结点缓冲区溢出问题，一旦数据发生溢出，会产生丢包，就会造成数据的重传，以及额外的控制包传送而消耗网络能量。图3中，当数据包的期限足够长的时候，两种方法的数据传递率都很高，当数据包的期限短的时候，两者的数据传输率都发生急剧降低。MCRICQR比QoS routing下降得稍微慢些，其原因在于，前者在调度时，综合考虑了信道情况、拥塞情况等因素，避免了不必要的等待和冲突。图4中，MCRICQR和QoS routing在数据生成速率低的时候，平均吞吐量都很高。随着数据生成率的增加，两者的吞吐量也随之降低。前者进行转发数据时，转发节点的选择基于尺度，竞争成为转发节点，处在最有利转发数据的节点，才会竞争成功，因此，其数据传输成功的概率就高，从而提高了网络的平均吞吐量。

图1 不同QoS路由平均包延迟Fig.1 Average packet delay for different routing schemes

图2 不同路由方法下网络生命时间Fig.2 Network lifetime for different routing schemes

图3 不同期限下包传递率Fig.3 Packet delivery ratio for different deadlines

图4 不同包生成率下吞吐量Fig.4 Throughput for different packet generation rates

5 结语

基于尺度的协同中继自主转发跨层QoS路由算法(MCRICQR)应用在WSN中。节点根据自身所处的位置、剩余能量、信道状况、中继队列通信流以及节点缓冲区使用情况，形成一个综合的度量尺度，根据尺度值进行竞争成为NHF、RFN、LPF节点，自主转发数据。仿真结果表明，MCRICQR方法能够根据网络状态及时转发数据，时延低，提高网络可靠性，具有较强的鲁棒性和自适应性;MCRICQR方法是基于尺度进行竞争自主转发数据，可以对网络进行负载均衡，提高网络吞吐量，延长网络寿命，保障了WSN的QoS需求。同时，MCRICQR方法不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算资源，它不会招致任何端到端的路由维护过程的过度开销，提高了能量效率。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y ，et al.A survey on sensor networks［J］.IEEE Comm，2002，40(8):102 －116.

［2］Laneman J N，Tse D N C，Wornell G W.Cooperative diversity in wireless networks:efficient protocols and outage behavior［J］.IEEE Trans Inform，2004，50(12):3062 －3080.

［3］Lin X，Shroff N B.The impact of imperfect scheduling on crosslayer congestion control in wireless networks［C］//IEEE INFOCOM，Miami，FL，USA，2005.

［4］David Tse，Pramod Viswanath.无线通信基础［M］.李 锵，周 进，等译，北京:人民邮电出版社，2007.

［5］http://www.omnetpp.org.

［6］Mahapatra A，Anand K，Agrawal D P.QoS and energy aware routing for real－ time traffic in wireless sensor networks［J］.Computer Communications，2006，29:437 －445.

Cross-layer QoS routing algorithm of metric-based cooperative relay in WSNs

Xu Nan1，Sun Yamin1，Yu Jiming2，Wang Hua3

(1.School of Computer Science and Technology，Nanjing University of Science and Technology，Nanjing 210094，China;2.School of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310014，China;3.School of Computer Science and Technology，Shandong University，Jinan 250023，China)

We proposed a cross-layer QoS routing algorithm which is metric-based cooperative relay initiative forwarding(MCRICQR).Nodes form a metric according to energy，channel，congestion and distance to sink.The node with maximal metric forwards or relays or leapfrogs the data in term of it’s own states.Simulation results show that MCRICQR can prolong the lifetime of network and guarantee the required QoS.It also can transmit data in time and load balance which improve the reliability and energy efficiency and throughput of WSN(wireless sensor network).

quality of service;cross-layer design;cooperative relay;initiative forwarding;wireless sensor network

TP393

A

1009－1742(2011)03－0045－05

2009－09－20;

2010－12－20

国家自然科学基金资助项目(60773101)

孙亚民(1946—)，男，江苏张家港市人，教授，博士生导师，主要研究方向为计算机网络与通信;E－mail:sunym@mail.njust.edu.cn