WSN中的最大冗余丢弃和覆盖传输拥塞控制

周小玲，付银莲

(1.广州铁路职业技术学院 基础课部，广东 广州 510430;2.华南农业大学 数学与信息学院，广东 广州 510642)

0 引 言

无线传感器网络(wireless sensor network，WSN)的应用已经扩展到诸多领域[1,2]，这种网络的一个显著特点就是在接收器附近传感器节点高度密集。随着网络规模的扩大，这些节点间的拥塞效应会变得更加明显。而这些节点的带宽是有限的，因此，为了最大化网络覆盖，选择合适的数据包进行缓冲和传输非常重要；一个数据包除了包含监测区域内某处事件的可用值外，往往还包含事件的位置。这些信息可以通过包含在数据包头中的节点ID或检测事件的节点坐标来传输。在前一种情况下，接收器节点需要采用预先计算的数据将节点ID映射到其位置。显然，这仅对预先规划的部署才是可行的。在后一种情况下，位置信息可以通过GPS或定位算法[3-5]来获得。

传感器网络的一个极其重要的性能目标是其覆盖范围。正如文献[6,7]所指出，覆盖有不同的特定表述，但一般认为是通过网络提供服务质量的一种度量。如果网络拥塞，则来自不同源的数据包在到达接收器之前有可能被丢弃，从而导致事件未被检测到或出现检测差错。因此，采用缓冲和调度机制来实现覆盖感知是很有用的。

尽管缓冲区管理和调度已经在传感器网络中得到了研究，但大多数现有研究或者仅考虑调度，或者仅考虑缓冲区管理，或者仅考虑覆盖，而没有在网络拥塞状态下同时将这三者加以考虑。文献[8]提出了一种无窗队列管理技术来避免传统同步显式ACK和停止-等待隐式ACK方案的问题，还执行一种区分争用控制，以减少任何必要的分组重传带来的拥塞；文献[9]提出了延迟数据包调度方案，但文献[10]指出，单独采用延迟调度可能导致次优能量使用，因而提出了一种替代调度算法，算法同时考虑无线电关闭和延迟调度策略。

在传感器网络中，事件检测至关重要。文献[11]提出的事件到接收器可靠传输利用端到端拥塞控制来确保网络事件可靠地传输到接收器；文献[12]提出了一种改进的AOMDV协议和网络拥塞控制及能耗均衡策略；文献[13]提出的拥塞缓解和避免协议采用开环、逐跳后压解决小时间段的拥塞，以及闭环、多源调节来解决更长时间的拥塞；文献[14]提出了一种拥塞控制和公平协议。

拓扑控制也是缓解拥塞和确保所需覆盖的另一种选择方案。探测环境和自适应休眠[15]就是一种拓扑控制协议，它关闭冗余节点以节省电池功率，只有保持感知覆盖所需的最小节点数量才能保持运行；文献[16]提出的覆盖控制协议采用了类似的思想，但增加了网络动态配置自身以提供所需覆盖程度的能力。

针对上述算法的单一目标性和不足，本文提出了一种最大冗余丢弃(maximum redundancy discarding，MRD)的缓冲区管理和覆盖传输(coverage transmission，CT)的数据包调度机制，机制在选择用于丢弃和传输的数据包时利用空间信息来提高覆盖范围。算法是完全分布式和应用独立的，不需要节点间发送信号，仅要求数据包携带其源节点的地理位置坐标；仿真实验结果表明，提出的算法机制能有效提高网络的覆盖范围。

1 问题构建

为简化起见，考虑监测区域A为一个单位正方形(如果是任意形状的监测区域，可以将其细分为单位正方形)，其中随机部署的无线传感器节点集合为N。令X1、X2、Y1、Y2为独立的随机变量，分别表示N中两个节点的坐标 (X1,Y1) 和 (X2,Y2)。 用R表示两个节点间的距离，这是一个正方形线拾取问题(square line picking problem，SLPP)[17]。R的概率密度函数为

(1)

R的累积分布函数为

(2)

令γ表示每个节点的感知圆半径。对于任意两个节点有R<2γ，如图1所示，则重叠感测区域为

图1 相距R且每个传感器的感知半径为γ的两个传感器

(3)

如果R<2γ且L(R)=0，假设γ<<1，则期望的重叠区域为

(4)

令集合Sj⊂N包含从N中随机选择的j个节点，由这j个节点获得的总覆盖率用C(Sj)表示。对于每个节点n∈Sj，n的效用定义为

(C(Sj)-C(Sj(〗n}))/πγ2

(5)

即与其它节点的感知圆没有重叠的n的感知圆的部分。

令节点s1∈Sj与n的距离为R1(<γ)，n(关于s1)的效用定义为

(6)

考虑Sk(〗n} 中全部节点的感知圆与n的感知圆有重叠的情形，设节点为s1,s2,…,sj且这j个节点与n的距离分别由随机变量R1,R2,…,Rj给出。由于节点的放置是相互独立的，所以n的效用为

(7)

如果考虑每个随机变量R1,R2,…,Rj可以取值的范围，则有j个重叠节点的n的期望效用为

(8)

如果我们构造Sj使得Sj中的每个节点与n的距离至少为h，则式(7)给出的期望效用就变成

(9)

图2所示为对于γ=0.12的单位正方形上n的期望效用与h的关系，从上到下的曲线对应于j=1、2、3、4、5、20和100。当增大n与全部其它节点间的最小距离h时，Ej[θ(n)] 增大。对于足够大的h，节点相距很远，效用为1。此外，当j增大时，Ej[θ(n)] 就小，因为节点之间可能存在很高的重叠或冗余。

图2 γ=0.12时的期望效用与h的关系

图2所示结果为本文提出的缓冲区管理和数据包调度算法提供了启发。当需要丢弃一个数据包时，就丢弃导致最小h值的数据包，删除其来增大全部节点间的最小距离。图2还表明，通过确保队列中剩余的k个数据包尽可能彼此远离，则每个数据包的期望效用就更高。同样，调度算法也能很好地选择与其它数据包的源节点尽可能远离的数据包。下面提出利用这些启发式思想的算法。

2 实现拥塞控制的缓冲区管理和数据包调度

2.1 虚拟队列

在描述实现基于最大冗余丢弃的缓冲区管理和基于覆盖传输的数据包调度算法之前，先引入虚拟队列的思想，如图3所示。从根本上说，虚拟队列存储最近传输的数据包的最前面部分。假设最前面的数据包的大小仅为总数据包大小的一小部分，则虚拟队列允许节点以最小内存开销缓存其传输历史。对于本文后续部分，当需要区分数据和虚拟队列时，我们将明确说明包含数据的队列的真实队列和虚拟队列。

图3 虚拟队列向真实(数据)队列添加历史

2.2 最大冗余丢弃的缓冲区管理

MRD的基本思想是：对于任意两个传感器节点，由它们报告的数据之间的相关性随着它们之间的距离的增大而减小。如果节点之间彼此靠得很近，则由两个节点报告的感测数据将存在很大程度的冗余。在拥塞期间，相比于丢弃靠得很近的节点的数据包，丢弃一组相距很远的节点的数据包可能会导致更多的信息丢失。

令Q为一个传感器节点的队列，它由两部分构成：一个长度为k个数据包的真实队列和一个长度为v个数据包的虚拟队列。将真实队列和虚拟队列分别称为Re(Q) 和Vir(Q)， 还将任意数据包pi的源节点ni称为Src(pi)，用d(ni,nj) 表示节点ni和nj之间的距离，其中d(·,·) 为欧氏距离函数。为简化起见，用d(pi,pj) 表示d(Src(pi),Src(pj))， 最后，令D(pi,S)=∑pj∈S(〗pi}d(pi,pj)。

如果当传入的数据包p到达时Re(Q)是满的，则采用以下规则找到两个靠得最近的数据包p1和p2：

(1)p1∈Re(Q)∪{p} 且p2∈Q∪{p},p1≠p2；

(2)∀pi∈Re(Q)∪{p} 且∀pj∈Q∪{p},pi≠pj，d(p1,p2)≤d(pi,pj)。

丢弃策略如下：

(1)如果p2∈Vir(Q)， 则丢弃p1；

(2)如果p2∈Re(Q)∪{p}， 当且仅当D(p1,Q∪{p})

该缓冲区管理算法的特性是，如果Q是MRD执行之前的队列，且Q′是丢包之后的队列，则∑pi,pj∈Qd(pi,pj)≤∑pm,pn∈Q′d(pm,pn)。 因此，当一个传感器节点遭遇拥塞时，队列中的空间会偏向于较高效用值的数据包。算法实现的伪代码如算法1所示。

算法1： 最大冗余丢弃算法实现伪代码

Receive-Packet(p)

(1)Q为长度为(k+1)+v的队列， 其中Re(Q)的最大长度为k+1且Vir(Q)的最大长度为v

(2)enqueue(Q,p)

(3)if length[Q]=k+1

(4) then Buffer-MGT(Q)

Maximum-Redundancy-Discarding(Q)

(1)dist←∞

(2)p1←Null

(3)p2←Null

(4)fori←1 to length[Re(Q)]

(5) do forj←i+1 to length[Q]

(6) do ifd(Q[i],Q[j])≤dist

(7) thenp1←i

(8)p2←j

(9)dist←d(Q[i],Q[j])

(10)ifp2>k+1

(11) then discarding(Q[p1])

(12) else ifD(p1,Q)

(13) then discarding(Q[p1])

(14) else discarding(Q[p2])

2.3 覆盖传输的数据包调度

当采用先进先出(first-in first-out，FIFO)调度算法时，调度器总是传输来自于队列头部的数据包，且在高效用数据包达到之前，可能传输大量低效用的数据包。此外，考虑到传感器节点的低带宽，高效用数据包传输之间的时间间隔可能很大。这个问题可以通过从队列中选择具有最高效用的数据包传输来解决，所以本节提出一种调度算法——覆盖传输(coverage transmit，CT)，它尝试选择最大化覆盖的数据包传输。

尽管寻找具有高效用数据包的基本思想与缓冲区管理问题相似，但它实际上比寻找具有低效用的数据包要复杂得多。这是因为当两个数据包非常靠近时，重叠或冗余与其它数据包高度无关。然而，只有当一个数据包与所有其它数据包具有最小的感知重叠时，它才有较高的效用。因此，寻找高效用或低冗余数据包需要同时考虑全部数据包，原理如下。

对于每个数据包pi∈Re(Q)， 令Vi={v|v是从Src(pi) 到Src(q)的一个矢量，其中q(Vir(Q) 且d(pi,q)≤2γ}。

图4 Src(pi)=N时数据包pi的Vi的计算

2.4 数据包超时

由于我们感兴趣的是传感器网络在最后一个Tc时间段提供的覆盖，而早于Tc的数据包对覆盖没有贡献。因此，我们从真实队列中丢弃比Tc更早的数据包。对于虚拟队列，将超时周期设置为1.5Tc。

3 仿真实验结果及分析

3.1 仿真环境及设置

仿真采用GloMoSim[18]提供的无线网络环境，它是一种可扩展仿真系统模型，在层与层之间提供了标准API接口函数，这样就可在不同层或开发人员之间建立快速的综合集成，以包含本文的缓冲区管理和调度协议；表1所示为用于GloMoSim仿真的参数设置。对于选择的参数，网络密集且感知密度为31.8，因此，平均每个点被31.8个节点覆盖。仅有一个接收器节点位于正方形区域的中心。每个节点的数据包或事件生成速率为一个数据包/10 s，在600 s的仿真期间是持续恒定的。对于每个传感器节点，事件生成的起始时间随机分布在0 s～30 s之间。

表1 用于GloMoSim仿真的参数设置

将虚拟队列的大小固定为24，这个虚拟队列长度足够大，以获得最好的可能性能；仿真中采用由200个传感器节点构成的两个网络拓扑，以计算得到的静态路线和平均跳数值分别为5.73和8.23，每个网络表示随机分布在一个区域内的节点的可能布局。一个是典型的较开放的区域，有最小的无线电干扰(称为网络I)，一个是在杂乱环境中，在这种环境中，大量障碍物阻挡无线电信号，干扰节点的视距通信(称为网络II)；一般来说，在杂乱环境的网络中的数据包必须进一步传输到达接收器。

将整个仿真时间间隔划分为不相交的间隔，每个间隔Tc(s)。将任意Tc间隔的定时覆盖定义为传感器字段的百分比，该传感器字段由接收器在该间隔中接收到的数据包覆盖，且该数据包在小于Tc前生成。这个指标度量了网络为被监测区域提供最新数据的能力；平均定时覆盖为测得的全部定时覆盖值的平均值。为便于比较，采用覆盖增益指标，定义为通过缓冲区管理和调度算法获得的平均定时覆盖相对于通过丢尾(drop-tail,DT)和FIFO获得的平均定时覆盖的比值，即得到的结果图形是通过组合C2、C3和C4获得的覆盖与组合C1获得的覆盖的比值，4种缓冲区管理和调度算法的组合如下：

C1：DT和FIFO；

C2：MRD和FIFO(即MRD+FIFO)；

C3：CT和DT(即CT+DT)；

C4：MRD和CT(即MRD+CT)。

在仿真中，改变数据队列长度D从8到64个数据包，考虑到一般性，仿真选取队列长度D=8和队列长度D=64，带宽β从38.4 kbps到153.6 kbps。

3.2 仿真实验结果

图5所示为网络I和网络II对于不同带宽的数据包传输比。从图5可见，对于相同的网络带宽，通常网络I比网络II有更低的包丢失。对于两个网络来说，当带宽为38.4 kbps时，数据包传输比低于10%，当带宽为153.6 kbps时，网络II仍然只传输30%左右的数据包，而网络I可传输80%以上的数据包。当然，这些结果与所采用的缓冲区管理和调度算法无关，只要不过早的丢弃且调度是工作守恒的。然而，当目标是最大化网络覆盖时，缓冲区管理和调度算法将产生很大差别，特别是在网络II中，包丢失很高。

图5 接收器接收的数据包百分比

图6所示为对于网络I、队列大小分别为8和64个数据包时的覆盖增益随带宽的变化关系。可见，对于较小的队列大小和带宽，缓冲区管理算法的影响最为明显，如对于仿真的缓冲区大小D=8和最低的带宽38.4 kbps，采用了MRD的组合算法MRD+CT和MRD+FIFO分别获得了最大1.36和1.28的增益，采用了CT的DT(即CT+DT)获得了最大1.24的增益。而随着带宽的增大，增益开始下降，且当带宽达到115.2 kbps时，全部组合算法的增益基本保持不变，这是因为当带宽较小时，同样的数据包传输队列会出现拥塞，如果采用了本文的缓冲区管理和覆盖传输算法，就会有效地提高覆盖增益。而当带宽增大时，同样的数据包传输队列就不会出现拥塞，所以无论哪种组合算法都不会影响覆盖增益；当D=64时，MRD+FIFO几乎没有增益，而MRD+CT和CT+DT仍然获得了较高的增益，但当带宽达到76.8 kbps时，增益开始下降，最后达到平衡；总的来说，MRD和CT的组合在仿真的整个缓冲区大小和带宽范围内执行最好。一般而言，覆盖传输的数据包调度起着更重要的作用，每个数据包的传输都需要调度，而MRD仅在缓冲区满时才执行。

图6 不同队列长度时网络I的覆盖增益与带宽的关系

图7所示为对于网络II得到的覆盖增益。网络II由于其到接收器较长的平均节点距离，因而有更高的包丢失，且通常增益更大。对于较小的缓冲区大小和较低的带宽，缓冲区管理更重要，对于较大的缓冲区和较高的带宽，数据包调度非常有用。因此，在存在较高包丢失的情况下，采用覆盖感知缓冲区管理和数据包调度算法可以提高覆盖增益的性能。同样，MRD和CT组合在仿真的整个缓冲区大小和带宽范围内执行最好。

图7 不同队列长度时网络II的覆盖增益与带宽的关系

4 结束语

针对无线传感器网络中的拥塞控制和覆盖率提高，本文提出了一种最大冗余丢弃的缓冲区管理和覆盖传输的数据包调度机制；仿真实验结果表明，在大多数情况下，采用MRD和CT获得了最佳覆盖增益；一般情况下，很难获得节点精确的位置坐标，所以对于未来的研究，我们将进一步研究如何获得节点近似坐标位置的技术和在这种情况下的算法性能，以及与精确位置坐标下的性能对比。