WSN中多跳网络能效和延迟控制优化研究

刘 云，王海花，向 婵

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

能量在无线传感网中是非常关键的因素，尤其是在给电池充电或者更换电池比较困难的环境中，因此高效节能是现在研究的热点[1-2]。然而在许多应用中比如火灾检测，数据的实时有效性也变得同样重要，因此必须权衡能耗和延时。

Younis O等人提出了HEED协议[3]，HEED协议是一种混合的高效节能分簇方法并且会定期更换簇头。分簇方法是基于节点剩余能量和另一个参数，比如节点到相邻节点的距离或节点的层级。HEED协议能均匀整个网络的簇头分布，从而均衡网络能量消耗；但是其必须迭代多次达到定期更换簇头的目的，因此会造成高昂的开销。

S Bai等人提出了DEAR协议[4]，该协议是一种多路径延迟限制和能量限制自适应路由协议。其考虑多种因素，比如可靠性、延迟和能量消耗，并且该协议允许数据包在网络中连续传输，即使传输时发生冲突。它能在解决多目标优化问题时，通过证明一个多项式时间算法来均衡延迟。然而由于算法的复杂度，节能和减小网络延迟会受限。

为进一步优化能耗和延迟均衡的问题，本文提出一种延迟能耗权衡多跳路由算法DETMR(Delay-Energy Trade-off in Multi-hop Routing)，该算法根据网络和能量模型提出新的能量消耗函数和端到端延迟函数，根据这两个函数选出满足端到端延迟限制的能耗最少的最佳路由，并且能权衡能耗和延迟的关系，提高网络整体性能。

1 模型分析

1.1 网络模型

采用如图1所示的网络模型[5]，所有的节点分散在同一区域中，并做如下假设：(1)所有的节点静止并且能量相同；(2)所有的节点都能感知自己的剩余能量并且根据传输的距离调节传输功率；(3)链路中的无线信号在所有方向上有相同的能量衰减；(4)如果通信的两个传感器没有在彼此的通信范围内，则必须由其它的节点转发；(5)所有的节点都能够操作转发模式和传输模式；(6)相邻节点的数据是相关的，因此簇头可以融合一部分数据以减少总的数据传输。

图1 网络模型

如图1所示的分簇网络模型，传感器节点分散在簇中，每个簇选出一个节点作为簇头，剩下的节点是成员节点，成员节点把收集的数据发送给簇头，簇头接收并融合收集到的数据经过多跳路由最后发送给汇聚节点。簇头融合数据的同时也转发数据[6]。传感器节点(尤其是簇头)能够在发送数据给汇聚节点的过程中调节到相邻节点的半径。

1.2 能量模型

能量模型采用文献[7]中的无线收发器能量耗散模型。接收lbit数据时消耗的无线能量如下

ER(l)=Ee×l

(1)

其中，Ee是电子能量消耗参数。

假设相邻节点传输的数据是相关的，则簇头可以融合冗余的数据使之成为一个固定长度的数据包。簇头融合m个节点的lbit数据消耗的能量为

EF(l,m)=m×Ef×l

(2)

其中，Ef是数据融合参数。

当距离是d时传输lbit数据消耗的能量如下

(3)

1.3 分簇过程

分簇过程以邻居发现阶段开始，然后汇聚节点以一定的功率发送ADV消息给所有的节点并完成初始化[8]。每个节点根据接收到的信号强度计算到汇聚节点的距离。

每个节点在发送ADV(ID，E)消息给相邻节点以及从相邻节点接收数据前等待的时间为τ=1/E，ID是节点标识符，E是节点的剩余能量。接收到ADV消息的节点之间比较能级，能级小的节点将会取消定时器从而成为成员节点。

候选簇头是能级比较高的一系列节点，而通信范围内的两个节点可能有相同的能级。为了解决这种情况，提出一种能量和延迟权衡(TED)方法来平衡能量消耗和端到端延迟。该方法通过调节参数α(α基于簇头的能量消耗)和参数β(β基于簇头到汇聚节点的距离)的值权衡能耗和延迟。如式(4)所示，TED表示选择的候选簇头。α和β是控制参数。α调节候选簇头对剩余能量的依赖，β调节候选簇头对距离的依赖。α和β值的范围都是[0,1]，并且α+β≠0。

(4)

Ei是候选簇头i的剩余能量，Et是其它候选簇头接收ADV消息时积累的能量，d(i，s)是候选簇头i到汇聚节点的距离。

若i是最终簇头，则其发出通知之前等待的时间为ω=1/TEDi。其它候选簇头收到最终簇头的公告，取消它们的TED定时并且在当前轮成为成员节点。分簇阶段完成之后，所有的簇头发送TDMA消息给成员节点并分配时隙[9]。

2 DETMR算法分析

DETMR算法是一个有连续回合的分布式方法，每一轮分为两个阶段[10]：分簇阶段和数据传输阶段。第一阶段的任务主要是建立一个分簇的网络拓扑并且建立多跳路由；第二阶段的任务是通过簇头传输从源节点到汇聚节点的数据。

2.1 计算端到端延迟

链路延迟D(i,j)测量从节点i到节点j的链路中数据包的延迟。定义链路延迟D(i,j)中节点的排队延迟是dQ，传输延迟是dT以及传播延迟是dP，用公式表示为

D(i,j)=(dQ+dT+dP)

(5)

其中，dT=l/φ,dP=d/γ；l是数据包长度，Ψ是链路带宽(bit/s)，d是簇头i到簇头j的物理链路长度，γ是在媒介中的传播速度(m/s)，dQ的值通过排队理论[11]计算。节点队列是M/M/1类型的。在这种队列中，输入是泊松类型，输出是指数随机变量，服务数是1。队列中的排队延迟可以用下式计算

(6)

μ是服务率，并且是一个指数随机变量，λ是新数据包的进入率，是泊松随机变量。

Dete(x,s)表示端到端的延迟，是指数据从离开源节点x到汇聚节点s接收经过的时间。定义Dete(x,s)表示如下

(7)

假设μ，λ，Ψ和γ是对所有簇头都相同的常数，U是从簇头x到汇聚节点s之间的一系列中间节点。

2.2 计算路由成本

定义式(8)表示从簇头i到j的链路消耗函数

(8)

其中,ER、EF、ET在式(1)～式(3)中已给出，ρ是节点剩余能量参数。

(9)

为了计算从簇头x到汇聚节点s路由的消耗函数，定义

(10)

2.3 DETMR算法描述

DETMR算法是为了找到从簇头x到汇聚节点s的最低消耗路由(最高效节能)。其中路由间端到端的延迟不存在延迟限制Δ。最小限制为

(11)

Rk是第k条路由，R′(x,s)是从簇头x到汇聚节点s中端到端的延迟满足Δ限制的一系列路由。Δ满足

Dete(Rk)≤Δ

(12)

通过考虑以上优化问题，提出了算法1用来找到至少k个消耗路由符合端到端的延迟限制。算法1伪代码如下：

1.SeR=Ø；SeR是从簇头x到汇聚节点s传输数据时选择的路由。

2.NoSa=Ø；NoSa是不满足延迟限制Δ的一系列路由。

3.计算costij，∀i,j∈C；C是一系列簇头，j可以是汇聚节点。

4.计算K(x,s)；K(x,s)是从簇头x到汇聚节点s可能的路由数。

5.找到至少k个消耗路由k-SR(x,s,k)；

6.while (k≠K(x,s)) do

7.Rk=k-SR(x,s,k)NoSa;

8.根据式(7)计算Dete(Rk);

9. if Dete(Rk)≤Δ then

10. SeR=Rk；

11. break；

12. else

13. NoSa=NoSa∪Rk；

14. k=k+1;

15. end if

16. end while

17. Return SeR；

算法根据式(8)中定义的消耗函数计算了从簇头i到j的每一条链路的costij值，接着利用深度优先搜索算法[13](DFS)计算从簇头x到汇聚节点s可能的路由数。在第5行，算法根据公式(8)～式(10)利用最短是k的路径找到至少k个路由。当找到消耗最少的路由Rk(k的原始值是1)后，算法利用式(7)计算这条路由的端到端的延迟Dete(Rk)。再检查端到端的延迟是不是满足特定的阀值Δ。如果满足，则选择路由Rk；如果不满足，把Rk移到NoSa。第7行将会移除不满足延迟条件的最小消耗路由。

经过证明[14]，算法总能在有限的时间内完成，因此是收敛的。并且计算复杂度是一个多项式函数[15]，因此完全适合应用在一个有有限个传感器节点的分散式算法。

2.4 数据传输

一旦簇间多跳路由创建成功，就会开始数据传输。每个节点分配传输时间之前会关闭无线电，然后在分配的时间内发送数据给簇头。簇头从簇内成员中接收数据。当所有的数据被接收后，簇头把接收的数据融合在单个的数据包来减少冗余和传输消耗的能量，然后把融合后的数据包发送给其它的簇头，其它簇头也按这种方式转发数据直到到达汇聚节点。在一段确定的时间之后，开始下一轮分簇过程。

由于成员节点只需要发送数据给簇头，因此每个成员节点j消耗的能量为

Emem(j)=l×Ee+l×ε1×d2(j)

(13)

其中，d(j)是成员节点j到簇头的距离。

而簇头需要融合所有的簇间数据以及转发数据给其他的簇头，因此能量消耗为

ECH(i)=ER(i)+EF(i)+ES(i)

(14)

ER(i)=l×Ee×(sCH(i)+r)

(15)

EF(i)=sCH(i)×Ef×l

(16)

(17)

ER(i)是簇头i接收所有的簇间数据消耗的能量，EF(i)是簇头i融合所有的数据消耗的能量，ES(i)是簇头i传输lbit的数据给其它簇头或汇聚节点消耗的能量，sCH(i)表示属于簇头i的成员节点的数量，r是延迟时间，d是从簇头i到下一跳的距离。

因此，每一轮总的能量消耗为

(18)

K是簇头的数量，N是网络中传感器的数量。

3 仿真分析

仿真基于Matlab，并与HEED协议、DERA协议进行对比，仿真参数如表1所示。

表1 仿真参数表

图2 不同函数下能量消耗比较

图3 能量消耗和端到端延迟权衡

图3表示能量消耗和端到端延迟变化曲线，为了便于观察，Dete和Etotal在同一个图中，表示随着转发者的数量变化，能量消耗和端到端延迟的变化趋势。通过分析两种曲线，能获得使能量消耗和端到端延迟获得权衡的最佳跳数。在这里，选择α=0.5，β=0.5,。从图中可以看出，当k=3(4跳)时，能使能量消耗和端到端延迟之间的权衡达到最佳，或k=2(3跳)也能达到目的。

图4 3种算法网络生命周期比较

图4表示随着通信次数的增加，3种算法活跃节点数的变化。仿真共进行了50轮(每轮1 s)。在前15轮，3中算法节点数量并没有明显变化；15轮之后，活跃的节点数都有明显的下降，并且HEED协议、DEAR协议与DETMR算法相比节点死亡更快，这是因为DETMR算法考虑到延迟控制问题，均衡了网络能量消耗，因此相比HEED协议、DEAR协议延长了网络生命周期。

图5 不同延迟限制下总的能量消耗对比

图5表示随着延迟限制的增加HEED协议、DERA协议和DETMR算法总的能量消耗对比。从图中可以看出，对于HEED协议、DERA协议随着延迟限制的增加总的能量消耗是不变的(HEED协议是67 J，DERA协议是48 J)，而对于DETMR算法，随着延迟限制的增加，总的能量消耗不断减少。

4 结束语

无线传感网中能量消耗和端到端的延迟是现在研究的热点。本文提出了一种延迟能量权衡多跳路由算法—DETMR，算法根据网络和能量模型提出一种新的能量消耗函数和端到端延迟函数。根据这两个函数计算能量消耗和端到端延迟，选出满足特定端到端延迟的最小能量消耗路由，从而确定数据传输的最佳路径。仿真结果与HEED协议、DEAR协议相比，DETMR算法能均衡网络能量消耗，延长网络生命周期。