刘　韬

(西南民族大学 计算机科学与技术学院, 四川 成都 610041)



WSNs中联合速率控制与时隙分配的效用优化算法*

刘韬

(西南民族大学 计算机科学与技术学院, 四川 成都 610041)

针对无线传感器网络(WSNs)，提出了一种联合节点数据采集速率控制与时隙分配的(JRCTA)算法效用优化。该算法建立统一速率控制与时隙分配的效用优化模型，将节点数据采集速率的优化控制与基于冲突避免的节点发送时隙分配结合起来，在控制网络延时性能的前提下，最大化汇聚节点在单位时间内所采集到的数据量。仿真实验结果表明，JRCTA算法具有较好的性能。

无线传感器网络; 速率控制； 时隙分配； 效用优化

0　引　言

在环境监测等传感器网络应用中，汇聚(sink)节点总是希望能够尽可能多地接收到来自各节点的感应数据，以达到增加监测准确性的目的。但由于节点间的相互干扰，每个节点的感应数据发送速率会受到限制，这就要求对各节点的感应数据采集速率进行优化控制；另外，为避免不同节点间的信号冲突，还要对各节点的工作时隙进行分配。

文献[1]针对网络流量的实时性和可靠性要求，提出一种基于优先级的服务区分速率控制策略，根据上游节点的优先级调整上游节点的发送速率；文献[2]提出了一种基于云模型的无线传感器网络(WSNs)拥塞和速率控制策略，通过节点拥塞度检测调节节点输入速率,但是没有考虑信号冲突及节点间相互干扰对节点发送速率的影响;文献[3]构建满足最小重传时延约束的传输层包长调整方程和实现方法，最终建立适合WSNs的速率调整机制，但是该方法并未考虑冲突，也未考虑节点的路由机制；文献[4]则将WSNs中的最大化吞吐量问题转换为最大流问题，但该研究同样没有考虑冲突、干扰等因素；文献[5]提出为控制误码率，网络中每个节点自适应的调节自己的数据发送速率，但是该协议只能适用于单跳网络中；文献[6]针对太阳能传感网的分布式数据采样率控制算法，通过调节节点在每个时段的采样率来控制节点的能耗，并优化网络效用。上述算法虽能优化节点的发送速率，但是均没有考虑信号冲突与数据时延性能。

针对现有研究的不足，本文提出了一种联合节点数据采集速率控制与时隙分配(joint node data acquiring rate control and timeslot assignment，JRCTA)跨层优化算法。该算法在冲突避免的基础上，以最大化效用为目标，通过基于对偶分解的分布式求解算法，优化分配节点的工作时隙以及节点的感应数据采集速率，从而在提高汇聚节点单位时间内的数据采集量和节点的延时性能间获得较佳平衡。

1　网络模型和传播模型

整个网络由一个汇聚节点(Sink)和多个传感器节点组成，假设网络具备如下性质：每个节点以一定速率采集数据并直接发送；节点发送数据的路由已由路由算法事先确定；每个节点发射功率固定为Pt；节点可以作为中继节点，每个节点的数据缓存足够大。

网络的整个数据发送过程分割为多个时间长度相等的数据传送周期，每个传送周期再划分为多个时隙。为避免冲突，需要将时隙合理分配给各节点，节点只在其分配的工作时隙内才能经由一条链路发送数据。使用二维数据As[L,M]来表示网络中各链路的时隙占用表，L表示网络中链路的数量，M表示一个数据传送周期内的时隙数量。如节点选择链路l，且在时隙t内发送数据，则As[l,t]=1。若某链路在某时隙内没有数据发送，则As相应的值为0。

2　冲突图

根据节点的路由,可以建立网络拓扑图，实例如图1中G所示,节点间的边表示无线链路。另外，为表示不同链路间的冲突关系，建立了冲突图。G所对应的冲突图G′如图2所示，冲突图中的节点表示网络中的无线链路，而图中的边表示该边两端的节点所代表的无线链路会发生冲突，不能安排在同一工作时隙。

图1　网络拓扑图G

图2　冲突图G′

结合拓扑图，冲突图的建立步骤如下:

1)对于G中每条无线链路，在G′中建立一个节点；

2)对于G中的任意一条无线链路l,发射节点为t(l),接收节点为r(l)。若存在另一条无线链路l′,当两条链路同时发射时，出现以下三种情况,两条无线链路会产生冲突:

a.接收端r(l)或r(l′)的信噪比ψ超过门限值。根据文献[7]，接收端r(l)的信噪比ψ可由式(1)得到

(1)

式中σ2为噪声功率，θ为正交因子，t为该链路的工作时隙，Fl为会对链路l产生干扰的链路集合，Pt为节点的发射功率。hij为以i为发送节点，j为接收节点的链路的增益。可由下式计算

(2)

式中λ为电磁波的波长，dij为传播距离，η为传播损耗系数，Gt与Gr分别为节点发送端与接收端的天线增益。

b.一条链路的接收节点是另一条链路的发射节点，即r(l′)= t(l) 或r(l) = t(l′)。

c.两条链路的接收节点为同一个节点，即r(l′) =r(l)。

3)对于G中冲突的两条无线链路,在冲突图G′中对应的节点间建立连线。

3　初始化时隙分配算法

为避免不同节点发送信号产生冲突，需要对每个节点在每个传送周期内的发送时隙进行分配，建立时隙占用表As。针对任一网络G的初始化时隙分配算法具体流程见算法1。

算法1初始化时隙分配算法

1)建立网络G对应的冲突图G′；

2)初始化时隙占用表As，所有元素的值均设置为0；

3)Foreach链路lin网络拓扑图G

a.t=1;

b.查看时隙占用表，并计算已使用第t个时隙发送数据的链路数量N(t);

c.若N(t)=0，则t确定为链路l的工作时隙，即设置As[l,t]=1，N(t)= N(t)+1,l设置为下一跳链路，返回a；

d.若N(t)=1,则查看冲突图，正在使用时隙t 的链路和l是否冲突：若不冲突，则As[l,t]=1，N(t)= N(t)+1,l设置为下一跳链路，返回a；若冲突，则t= t+1,返回b；

e.若N(t)>1,则根据式(1)重新计算增加链路l后，每条使用时隙t 的链路接收端的信噪比ψ，若ψ仍然小于一门限值，则As[l,t]=1，N(t)= N(t)+1,l设置为下一跳链路，返回a；否则，t= t+1,返回b。

End

利用算法1可以获得图1中所表示网络G的时隙占用表As，并根据As建立发送时隙分配示意图，如图3所示。其中，每个数据传送周期内的时隙数量M为3。

图3　图1所示网络的时隙分配示意图

4　基于效用优化的节点速率的分布式控制

假设网络中任一节点s的数据采集速率为Xs，节点的效用函数为U(Xs)，它是严格凹且单调增的二次可微函数。拟采用网络效用最大化的办法来优化各节点的Xs。效用优化模型还必须满足两个约束条件：一个是节点的数据采集速率约束条件；另一个是链路容量约束条件，链路容量由香农公式计算

(3)

Wl表示以节点s为发送节点的链路l的带宽，ψl表示链路l的信噪比,它可由式(1)计算。因为节点仅在分配给它的发送时隙内发送数据，节点s的网络注入速率为MXs；Setchild(s)为节点s在路由树中的孩子节点集合。经变换，式(3)可以转换为

(4)

为方便表示，假设

(5)

结合上述约束条件，网络的效用优化模型可总结为

(6)

s.t.Xmin≤Xs≤Xmax,∀s∈N

(7)

Xs≥us,∀s∈N

(8)

式中网络效用为所有节点效用之和，N表示所有传感器节点的集合；式(7)表示节点的数据采集速率约束条件，Xmin和Xmax分别表示节点的最小和最大数据采集速率；式(8)表示节点的链路容量约束条件。

因为效用函数U(Xs)是严格凹且单调增的二次可微函数，所以,问题(6)是凸优化问题，采用对偶分解法来求解该问题。该问题对应的拉格朗日函数为

(9)

式中μ≥0为拉格朗日乘子。对于一个确定的μ，各子节点对应的对偶分解子问题的解为

s.t.Xmin≤Xs≤Xmax

(10)

由于U(Xs)是严格凹函数，所以,式(10)的最优解唯一。可以使用梯度投影法求解μ

μ(z+1)=[μ(z)-α(Xs-us)]+

(11)

综上所述，基于对偶分解的节点优化数据采集速率分布式求解算法描述如算法2。

算法2节点数据采集速率分布式求解算法

初始化：设z=1,μ是任意非负值，Xs设置为Xmin，T=Φ,T*=Φ

Repeat

fors=1,2,…,n

a.节点s广播自己的Xs的值；

b.每个节点接收和转发来自其干扰节点和孩子节点发来的Xs的值；

c.节点s计算U(Xs)，并使用式(5)计算us；

e.节点s使用式(11)更新μ(z+1)，并广播；

end

z=z+1;

ifT={Xs,s=1,2,…,n}

T*= T

else

T={Xs,s=1,2,…,n}

end

UntilT*≠∅

ReturnT*。

5　JRCTA算法

每个节点到达汇聚节点的路由形成了一颗路由树，根据本文所提的调度原则，每个数据传送周期中每个节点仅占用一个发送时隙发送数据，即感应数据在每个数据传送周期仅前进一跳，那么在路由树中所处的层次为h的节点的数据需要经过h跳才能到达汇聚节点，所以,该节点发数据到Sink的时延期望为hMT(T为一个发送时隙的长度)。在路由不变的情况下，要减小数据发送到Sink的时延，就要减少每个数据传送周期的时隙数量M,但时隙数量过低会造成许多节点使用同一个时隙发送数据，这加大了节点间的相互干扰，增加了节点的信噪比，也限制了和节点速率相关的网络效用的提高。所以，将网络速率控制和时隙数量M的确定，以及时隙分配归纳为一个效用优化问题，进行联合优化。优化目标函数F修改为

(12)

优化目标为最大化 F。式(12)采用加权组合法求解这个两目标的联合优化问题，其中，w1与w2为加权因子，w1∈[0,1]为本征权，反映各指标相对重要性，而w2为校正权，用来调整两个优化目标在数量级上差别。这样，最大化网络效用与最小化时隙数量M构成了一个两目标的数学规划问题。基于上述优化模型，提出了一种JRCTA跨层优化算法(算法3)来求解问题。

算法3JRCTA优化算法

1)利用算法1进行初始化时隙分配，确定初始化的M,计算并获得时隙占用表As。

2)利用算法2计算当前时隙分配下的最大化网络效用和节点优化采集速率，并使用式(12)计算优化目标函数F的值。

3)寻找被最多链路同时占用的时隙t,如果有k 条链路使用该时隙 ，则挑选k/2 条链路，将它们的发送时隙设置为第M+1个时隙，并修改时隙占用表As。

4)利用算法2重新计算最大化网络效用，并使用式(12)计算修改后的优化目标函数F*的值。

5)F与F*比较，若F*>F，则F= F*， M=M+1,确定修改时隙占用表，返回(3)；若F*≤F，则说明扩大M无法增大优化目标函数的值，取消此次修改并退出。

使用算法3对图1所示网络在初始化时隙分配的基础上继续优化，可得出M 扩大为4，链路k的发送时隙变动到第4个发送时隙上。

6　实　验

利用OPNET作为仿真平台对JRCTA算法的时延性能进行评估。如无特别指定，实验中的参数设置如下:Wl=20kHz,噪声带宽BN=30kHz,噪声功率σ2=5×10-10mW,η=2,θ=1/256,λ=0.3m,GtGr=4,节点功率为1mW,节点数据采集速率范围为[1kb/s,300kb/s]。节点效用U(Xs)=log(Xs)。

首先，网络采用图1所示的实验场景，共7个节点，节点A为汇聚节点。网络的每个数据传送周期采用不同数量的发送时隙,根据算法2计算每个节点的优化速率，并经过仿真获得网络的效用，其结果如图4所示。

图4　不同M值下的网络优化效用

从图4可以看出，当节点的每个数据传送周期内的时隙数量M开始增加时，网络效用不断提高，这是由于不同节点可以安排在不同的时隙内发送，减小了节点的相互干扰，可以提高节点速率；但当M增加到等于或超过节点数量时(M≥6)，网络效用不再增加,实验结果与分析结果一致。

图5反映了当本征权w1分别为1和0.5时，不同节点数量的网络采用JRCTA算法获得的节点速率后的网络效用值。w1为1时，根据式(12)，优化过程中实际上并没有考虑网络的时延性能。从图5可以看出：w1取0.5时网络所获得的效用要大于w1取1时的网络效用，这说明JRCTA算法的时隙优化分配通过恰当增加每个数据传送周期内的时隙数量，减少了同一个时隙发送数据的节点数量， 有效减少了节点间的干扰，提高了网络效用。

图5　不同节点数量下的网络优化效用

7　结　论

提出了一种WSNs中JRCTA的效用优化算法。该算法在冲突避免的基础上，建立统一速率控制与时隙分配的效用优化模型 ，并通过基于对偶分解的分布式的优化算法求解该模型，优化分配节点的工作时隙，并获得节点的优化数据采集速率。最后，实验结果表明：本文所提算法在控制网络延时性能的前提下，最大化汇聚节点在单位时间内所采集到的数据量。

[1]刘洪涛，程良伦.基于优先级的服务区分和速率控制策略[J].计算机应用，2011,31(6)：1458-1460.

[2]赵永辉，史浩山.基于云模型的无线传感器网络拥塞及速率控制策略[J].传感技术学报,2010,23(1):133-138.

[3]朱晓亮，杜旭，杨宗凯，等.无线传感器网络实时媒体传输速率控制机制[J].小型微型计算机系统，2007,28(2):199-203.

[4]马宁,李开宇,吴寅,等.基于最大流的能量采集型无线传感器网络路由算法[J].传感器与微系统，2013，32(1):131-134.

[5]Koutsopoulos I,Stanczak S,Feistel A.Transmit rate control for energy-efficient estimation in wireless sensor networks[C]∥Global Telecommunications Conference,GLOBECOM 2010,Miami,Florida,USA:IEEE,2010:1-5.

[6]Zhang Y M,He S B,Chen J M,et al.Distributed sampling rate control for rechargeable sensor bodes with limited battery capaci-ty[J].IEEE Transactions on Wireless Communications,2013，12(6)：3096-3106.

[7]He Shibo,Chen Jiming,Yau D K Y,et al.Cross-layer optimization of correlated data gathering in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2012，11(11):1678-1691.

An utility optimization algorithm based on joint rate control and timeslot assignment for wireless sensor networks*

LIU Tao

(School of Computer Science and Technology,Southwest University for Nationalities,Chengdu 610041,China)

A joint node data acquiring rate control and timeslot assignment (JRCTA) algorithm is proposed for wireless sensor networks(WSNs).An unified utility optimization model based on rate control and timeslot assignment is established,the optimization control of data sampling rate is combined with timeslot assignment collision avoidance.It can maximize total quantity of data collected by sink node per unit time on the premise that end-to-end delay is restricted.Simulation results show that JRCTA algorithm performs well.

wireless sensor networks(WSNs); rate control; timeslot assignment; utility optimization

10.13873/J.1000—9787(2016)09—0144—04

2015—10—21

国家民委科研项目(14XNZ030);四川省教育厅科研重点项目(15ZA0395)

TP 393

A

1000—9787(2016)09—0144—04

刘韬(1978-),男,四川宣汉人,博士后,副教授,CCF会员,主要研究方向为无线传感器网络。