无线传感网络的广播时效性研究

王 梅，彭丹丹，张壮壮

南京信息工程大学 电子与信息工程学院，南京210044

由于移动无线服务爆炸式增长，实时信息的传播在实时系统和网络中变得越来越重要。例如在车联网络中[1]，车辆需要及时共享其状态位置（如位置、速度、加速度），以确保行驶安全。然而，无论是传统的延迟还是吞吐量，都不太合适用来度量信息的新鲜度[2]。具体来说，当延时很小时，如果传输不太频繁的话，接收到的数据包并不总是新鲜的；当吞吐量较大时，如果数据经历较大的队列延迟时，接收到的数据也可能不新鲜。因此，“信息年龄”（age of information，AoI）这一概念在2011年被Kaul等人提出作为衡量信息广播系统的时效性的重要指标。AoI 指最新成功接收的数据包的当前时间与生成时间之间的时间差，即接收器处最新可用的数据包的年龄。AoI用来描述接收到的数据包的新鲜度，当吞吐量非常低或非常高时，AoI就会很大。因此，AoI被认为是比吞吐量和延迟更好的及时性度量。Kaul 等人基于经典的排队理论方法分析了M/M/1、M/D/1和D/M/1[1]在不同服务策略下（包括先到先服务（first come first served，FCFS）[1，3]和后生成先服务（last generated first served，LGFS）[4]）的信息年龄。

传统的AoI是从接收方考虑接收信息的时效性，非常适用于点对点通信。然而，在许多无线传感网络中，节点需要在整个网络中传播它的数据包。例如，当一辆车发生事故时，该车应尽快将此紧急信息传播到整个车辆网络，以便其他车辆能够做出及时且适当的响应。当汽车接收到来自任何邻居的新消息时，不管消息何时生成，消息是否比先前接收到的消息更新鲜，AoI 都会发生变化，因此，本文从发送机的角度来研究网络的广播信息年龄（broadcast age of information，bAoI）。bAoI被定义为当前时刻减去刚刚广播成功的那个数据包的生成时刻，即最新成功广播数据包的年龄。尽管bAoI与AoI的定义相似，但是bAoI能够研究每个信息源的广播行为和发送到每个信息源的一跳邻居的数据包的及时性。

在无线传感网络中，介质访问控制（medium access control，MAC）协议决定了无线信道的使用方式，通过在传感器节点之间建立链路可以保证节点公平有效地分配有效的通信资源。载波监听多路访问/冲突避免（carrier sense multiple access with collision avoidance，CSMA/CA）协议是应用得最广泛的一种媒体访问控制方案。目前，人们对基于CSMA/CA 协议的信息传播有了广泛的研究[5-8]。文献[5]在饱和情况下建立了马尔可夫链模型来分析网络的吞吐量性能，然而典型的网络条件是非饱和的，文献[6-7]进一步将此模型扩展到不饱和的环境来进行研究，文献[8]针对不同的路由协议（如flooding、pflooding）在网络覆盖方面的广播可靠性进行了综合分析和比较。文献[9]讨论了网络节点间的公平性问题。

本文研究了一种基于时隙CSMA/CA 的节点均匀分布的无线传感网络。在每个时隙中，每个节点以一定的概率生成一个数据包，并根据时隙CSMA/CA协议将其广播给邻居。本文建立该网络的等效传输模型，分析研究节点的碰撞概率和传输概率。在此基础上计算网络的平均bAoI。通过理论和仿真验证，节点密度和到达率等因素对网络的平均bAoI 有较大的影响。平均bAoI 与密度和到达率的变化曲线是凸的。也就是说，当到达率很小或很大时，平均bAoI会增加，并在中间达到最小值。选取合适的到达率和节点密度可以使网络的平均bAoI达到最小。

1 系统模型

考虑如图1所示的无线传感器网络模型，该无线传感器网络由M个节点构成，均匀分布在一个面积为A的区域内，则此时的节点密度为ρ=M/A。无线传感器网络中的节点都有相同的通信半径r，若任意两个节点之间的距离d小于或等于通信半径r，即d≤r，则称这两个节点互为邻居节点。节点服从均匀泊松分布，度的分布为：

图1 无线传感网络模型Fig.1 Wireless sensor network model

其中，泊松分布的参数为η=ρπr2。

将时间划分为若干相同大小的时隙，每个节点都以固定的概率在每个时隙首端生成一个数据包。如果节点在这一时隙没有接收到来自其邻居的数据包，其自身产生的数据包就被放入缓存队列中，并在稍后广播。否则，自身产生数据包将被丢弃，接收到的数据包将被保存和广播。

网络中的所有节点共享同一信道，并根据时隙CS-MA/CA 协议进行传输。在该协议中，每个节点由一对整数(s,t)建模。其中s指的是退避次数，从0开始，每一次传输尝试导致冲突时就会增加1，最多可增加到smax；t指的是退避时间（看作一个计数器），在(0,Ws-1) 间均匀选择。其中Ws=2sWmin，Wmin为最小竞争窗口。为了避免冲突，每一个节点在发送数据前需要等待一个退避时间。当计数器减到0的时候，节点将传送数据。如果与其他节点的传输发生碰撞，节点将进行另一轮的退避，相应的退避次数也会增加。

本文研究的网络是非饱和的，一些节点没有数据包可以传输，因此引入(0,t)e表示一个刚发送完数据包但是缓存没有数据包等待的节点的状态，其中t∈[0,W0-1]。当s>0 时，表示该节点发生了冲突，此时节点的缓存中至少有一个等待传输的包。因此，在这样的状态下，退避次数s=0。pidle用来表示当计数开始减少时节点缓存没有数据包等待发送的概率，1-pidle用来表示在非饱和状态下计数器开始减少时节点缓存至少一个包等待发送的概率。

与传统的AoI 从接收者的角度度量数据包的新鲜度不同，本文提出了一种新的度量方法，即广播信息年龄（bAoI）。

定义1广播信息年龄等于当前时间m和最新成功广播的数据包的生成时间U(m)之间的差值：

本文主要研究网络的平均单跳的bAoI，可以表示为：

图2 展示了bAoI 和AoI 变化的示例路径。从图中可以看出，bAoI在时间上呈线性增长，并重置为一个较小的值（最新成功广播的数据包的年龄）。在这种情况下，虚线曲线所示的AoI的物理意义并不十分清楚。如果一个节点接收到一个新的数据包，而这个数据包比之前从其他邻居收到的数据包要新鲜，那么该节点的AoI将被重置为更大的值。

图2 bAoI和AoI的样本路径Fig.2 Sample paths of bAoI and AoI

2 等效模型

基于连续离散模型计算节点的新到达率，从而得到数据包的到达时间间隔分布；建立等效传输模型计算数据包的服务速率从而得到服务时间分布。

2.1 连续离散模型

假设每个节点在时隙首端以概率p0生成一个数据包。那么数据包k和数据包k+1 到达的时间间隔（即到达时间间隔Xk=mk+1-mk）是参数为p0的几何分布，到达过程是Bernoulli 过程。经过多次广播后，每个节点的缓存中不仅包括由它自身生成的数据包，还有接收到的由该节点的邻居转发的数据包，则此时新到达率p大于初始到达率p0。然而，在离散时间状态下，新到达率的计算比较困难。因此，考虑在连续时间状态下进行研究。

通过在指数和几何分布之间建立一个连续-离散模型来计算在离散状态下的新到达率。如表1所示，伯努利过程是泊松过程的离散化，即指数分布是几何分布的连续模拟。

表1 泊松过程与伯努利过程Table 1 Poisson process versus Bernoulli process

在已知离散状态下的到达率p0的情况下，连续时间状态下的初始到达率λ0可以表示为：

在连续时间状态下，可以将节点自身生成的数据包与接收相邻节点转发的数据包的过程看作一个新的泊松过程，该过程具有新的参数λ。因此，节点的新到达率λ与三个参数有关，即自身到达率λ0、邻居到达率和转发概率pfw。

考虑到节点不接收自身已经广播的数据包，新的到达率λ可以得到：

通过简化计算，可以得到新的到达率λ的表达式：

那么，在离散状态下节点的新到达率p可以表示为：

2.2 传输模型

根据文献[10]，利用发送概率ptx和碰撞概率pcl建立了一个等效的传输模型。具体来说，发送概率就是每个节点在每个时隙发送数据包的概率；碰撞概率指的是节点在传输时发生碰撞的概率。这两个概率不管重传次数还是退避状态，都是相同独立的常数。

根据文献[6-7]可以得到发送概率和碰撞概率的计算公式。再结合文献[11-12]中的化简方法，这两个公式可以表示为：

由于每个以r为半径的区域的节点数N是泊松分布，每个节点的平均碰撞概率可以写成：

假设在每个时隙中，每个具有非空缓冲区的节点尝试以概率ptx来广播其数据包，会以概率发生碰撞。结合方程（8）和（9）可以求解ptx和。

当一个节点向其邻居发送数据包时，只有当该节点获得信道并且没有发生冲突时，发送才会成功。因此，成功广播的概率（也是数据包的服务率）可以表示为：

将节点获取信道并成功地传递数据包k的时间表示为Sk。那么，Sk是参数为μ的几何分布，概率分布可以写成：

3 网络的bAoI

首先根据已知的到达间隔时间和服务时间的统计特性建立排队模型，然后计算第P(P>1) 跳的平均bAoI。基于以上结果，进一步计算每个节点广播自己生成的数据包时的平均bAoI。

3.1 排队模型

由于经过多次广播，节点的缓存中不仅包含来自自身的数据包，还包含接收的来自相邻节点的数据包。因此，在每个时隙首端，数据包以概率p到达。数据包的到达时间Xk是呈几何分布的，可以得到Ε[X]=1/p，。服务时间Sk也服从几何分布，有Ε[S]=1/μ。

由此可知节点的广播过程为Geom/Geom/1 排队模型，即到达过程为Bernoulli 过程，服务过程是几何过程。根据文献[13]，一般Geom/Geom/1 队列中，节点缓存为空的概率可以表示成：

由于式（8）和（9）是非线性的，需要一个数值算法来进行计算。基于式（13）给出的空闲概率，本文提出了一种迭代算法来计算ptx和，具体如下所示。

根据文献[14]，系统时间Tk是数据包k的等待时间与服务时间之和，服从参数为1-υ的几何分布：

3.2 第P(P>1) 跳的广播信息年龄

离开时间间隔Yk表示两次连续成功广播的数据包之间的时间。根据文献[14]可知，对于Geom/Geom/1排队模型，离开时间间隔服从参数为p的几何分布。

数据包k-1 的系统时间Tk-1可以表示为：

由于服务时间Sk与到达间隔时间Xk相互独立，可以得到：

因为Wk=max(0,Tk-1-Xk)，所以Xk与Wk相关。根据文献[3]，构建一个辅助函数H(z)来计算Ε[XkWk]，如下所示：

利用辅助函数H(z)，可以得到：

根据式（16）和式（18），第P(P>1) 跳的平均bAoI可表示为：

3.3 第一跳的广播信息年龄

在每个时隙中，每个节点都以概率p0生成自己的数据包，到达时间间隔是呈几何分布的，因此可以得到。离开时间间隔服从参数为p0的几何分布。

与Xk之间的比值R可由p0与p之间的关系求得，因此比率的期望值可表示为：

其中Ε[XkWk]由式（18）给出。

第一跳的平均bAoI可以表示为：

因此，在已知跳数h的情况下，网络的平均bAoI可以表示为：

4 仿真结果

为了验证提出方法的有效性，用蒙特卡罗模拟来验证计算结果。最小竞争窗口Wmin=16，最大退避次数smax=3，通信半径r=6 m，初始到达概率p0=0.01，转发概率pfw=0.1，跳数h=2。

4.1 节点密度的影响

图3（a）和图3（b）分别展示发送概率和碰撞概率随节点密度的变化情况。从图中可以发现，发送概率ptx和碰撞pcl是密度的函数。首先，可以看到发送概率ptx随着密度ρ的增加而减少，而碰撞概率pcl随着密度的增加而增加。这是因为当节点密度变大时，每个节点将有更多的邻居节点和更多的传输争用。这样，碰撞概率就会增加，而传输碰撞的增加，则会导致传输概率变小。

图3 发送概率和碰撞概率随节点密度的变化情况Fig.3 Change of transmission probability and collision probability with node density

图4 反映了平均bAoI 随节点密度ρ的变化情况。从图中可以发现平均bAoI的理论结果与蒙特卡罗结果基本符合。结果表明，平均bAoI 是关于ρ的凸函数。平均bAoI 随ρ先减小，后随ρ增大而增大。当ρ较小时，平均bAoI 较大。当ρ变大时，新到达率p也变大。在确保的情况下，当ρ接近最大密度时，平均bAoI 将趋于无穷大。这是因为当节点密度增加时，数据包生成得非常频繁，导致碰撞也发生得更频繁。

图4 节点密度ρ 对平均bAoI的影响Fig.4 Average bAoI versus node density ρ

4.2 初始到达率的影响

初始到达率对平均bAoI的影响由图5所示，其中节点密度ρ=0.04。从图中可以发现平均bAoI 也是关于p0的凸函数。平均bAoI先随着p0的增大而减小，后随着p0增大而增大。由于新到达率p随初始到达率p0的增大而增大，在接下来的跳数中，每个节点将在每时隙首端以概率为p生成数据包。具体地说，当p很小时，平均bAoI较大。这是因为队列中的数据包较少，导致系统的等待时间更长。当p变大时，数据包生成得十分频繁，相应的平均bAoI也很大。

图5 初始到达率p0 对平均bAoI的影响Fig.5 Average bAoI versus arrival rate p0

从图4 和图5 可以看出，节点密度ρ和初始到达率p0的变化都会引起新到达率p的变化，为了减少网络的平均bAoI，节点密度或初始到达率既不能太大也不能太小。

5 结束语

本文提出了一种基于时隙CSMA/CA 协议的无线传感网络中度量信息时效性的方法。提出的广播信息年龄从发射机的角度量化了信息的新鲜程度。首先，根据时隙CSMA/CA 协议，推导节点广播成功的概率，结合对节点的到达过程的分析，推导出平均广播信息年龄的闭式表达式。仿真结果表明，节点的密度和初始到达率对平均bAoI有较大的影响。可以合理地控制节点的信息产生过程和信息转发过程，降低信息的碰撞概率，提高信息传输的成功概率，提高信息广播的时效性。

本文考虑的是每个数据包可以在一个时隙中传输完成的情况。对于数据包需要更多传输时隙的情况，基于服务器休假排队的平均bAoI 可以得到，并将在以后的工作中进行研究。