注：重庆市科委自然科学基金项目资助（CSTC，2005BB2198）
摘 要:：无线传感器网络（WSN）的MAC协议主要采用基于CSMA/CA的DCF机制，上述协议的能源效率随网络中竞争节点个数和负载的增加而迅速恶化。研究发现，CSMA/CA可以认为是1-坚持CSMA和p-坚持CSMA的混合体^[3]。本文提出了一种状态检测与竞争节点个数的自适应优化机制，ABM（Adaptive Backoff Mechanism），同时引入了信号流图模型这种新的方法来进行数学建模。根据相关数学模型的分析，p与系统参数存在着一定的数学关系，竞争节点个数和负载的变化都会引起p的改变，因此通过p的变化对相关参数进行动态调整，从而有效地改善了协议的整体性能。同时给出了相关模型和计算的详细说明，最后实验仿真，新的方法能够根据竞争节点个数和负载的变化对系统性能进行整体优化，在能量效率方面明显优于标准的CSMA/CA的DCF机制。
关键词：WSN；p-坚持CSMA；状态检测；ABM
中图分类号：TN925.93    文献标识码：A    

一、引言

无线传感器网络（WSN）是为中短距离、低速率而设计的无线数据传输网络。适合用于钢铁炼钢温度监控，蔬菜大棚温度、湿度和土壤酸碱度监控、煤气抄表等领域。WSN的MAC协议主要采用CSMA/CA的DCF机制，其核心思想是：当发现碰撞后，节点采用二进制指数回退的方式避免再次碰撞。但是WSN又有许多不同于传统无线网络的特点，其中一个很重要的特点是采用微型电池供电，能量受到限制。当将其用于一些特殊环境时，可能无法为其更换电池。因此我们有必要对CSMA/CA的DCF机制做出改进，使之更加适合WSN的应用。

许多学者利用数学建模的方法分析与优化协议的相关性能，Cali在文献[1,2]和Bianchi 在文献[4]中，分别对CSMA/CA的p-persistent机制和二进制指数回退机制进行了建模分析。其后，在Bianchi的模型基础上，Ziouva，Wu和Yang等人对相关模型作了进一步的完善工作。上述研究发现，CSMA/CA的DCF机制的性能随无线局域网中竞争节点个数和负载的增加而迅速恶化，协议的相关参数(例如CWmin(minimum contention window)对协议的性能有着主要的影响，使用固定参数难以保证不同网络负载情况下的协议性能。举例而言，对于较少的竞争节点，采用较小的CWmin可以有效地减少信道空闲时间从而提高信道的利用率；反之，对于较多的竞争节点，较大的CWmin则可以有效地降低发生碰撞的概率。因此，理想的CSMA/CA协议，不仅需要采用简单、高效的机制，也必须根据网络的负载情况动态调整协议的参数。

要判断实际的网络负载情况，首先需要对系统中竞争节点的数目进行测量与估计。文献[5]提出了一种基于Kalman和ARMA滤波的方法，尽管它是一个新颖的精度较高的估算方法，然而，相对于实际的无线网络环境，这一方法的前提十分苛刻，相关的信息需求量大，计算过于复杂，并且没有考虑到随机丢帧和隐藏节点等问题。因而，上述滤波的方法很难被直接采用。

二、理论模型与性能分析

本文用信号流图模型来分析CSMA/CA的性能，并假定：（1）所有节点的发送速率都是相同的；（2）饱和流；（3）理想信道；（4）不使用RTS/CTS；（5）无隐藏节点。

p-坚持CSMA使用的是分时隙（slot）的介质访问控制方法，即时间被分成离散的区间（时隙）。当节点侦听到信道空闲时，以给定的概率p在一个随机分配的时隙发送报文（节点对任意一个时隙占有的概率为p），以概率q＝(1－p)把发送推迟到下一时间，重新监听信道。每一帧的发送总是在时隙开始时启动。

1、系统模型的建立

设有M个节点采用p-坚持CSMA参与竞争信道，设每个终端的最小碰撞窗口为W₀，最大碰撞窗口W_m=2^mW₀，W_i=2ⁱW₀，i＝0，…，m。对于节点，消息包的发送是重复的，一个包接着一个包，两个包之间经历的过程可以描述节点的能量效率。此外，当信道空闲时，这些过程是无记忆力的，也就是说节点在下一个时隙的状态和过去是独立的。因此我们可以把节点从空闲到成功发送数据这个过程定义为一个系统，由相应的数学模型算出该系统的传递函数，通过传递函数我们就得到该节点的能量效率。把一个节点从产生一个消息包到成功的发送这个包所经历的过程看作一个系统，则这个系统要经历以下几个状态：

(1)         空闲（IDLE）：信道空闲，没有节点发送数据；

(2)         冲突(COL)：节点传送的数据包发生冲突，不同的节点同时发送数据；

(3)         忙(BUSY)：信道忙，其它节点获得了信道的使用权；

(4)         发送(TX)：节点获得了信道的使用权并且成功的发送了数据。

尽管上述过程状态不是马尔可夫过程，但是事件序列相应的状态跃迁构成了一个嵌入马尔可夫链，因此我们能够确定从i状态到j状态的n步转移概率p_ij(n) ^[6]。

P_ij(z)=                             （1）

式中，P_ij(z)—信号流图的传递函数，P_ij(z)z是状态跃迁图（state transition diagram）中i到j状态的增益，P_ij(n)其中是马尔可夫链中的一步转移概率，z是单位能量因子^[7]。我们可以通过流图简化方法(flow graph reduction methods)来确定信号流图的传递函数，信号流图定义的所有节点都要经历上述的状态，如图1所示。Tx(z)，Busy(z)和Col(z)分别是进入TX，BUSY和COL状态并且退出各自状态的传递函数。如果定义H(z)为进入IDLE状态直到TX状态(成功发送数据)的传递函数，则：

其中E_cs和E_t分别为节点在监听状态及其发送状态下，每个时隙消耗的能量。a、b、d、e（冲突概率）为进入各自状态的概率，利用概率统计的知识有：

， ，

，                (3)

该帖子于2008-5-9 11:46:10被 在那里 编辑过

节点进入TX状态之后将会退出这个系统，表示成功发送了一个包，并且消耗能量为NE_t（假设每个包的长度为N个时隙）；从进入COL状态到返回IDLE状态消耗的能量为NE_t；节点在BUSY状态持续监听N个时隙再进入BUSY状态消耗的能量为NE_cs，因此：

 Tx(z)=   ，Busy(z)= ，

Col(z)=                                 (4)

通过(2)、(3)、(4)，便可以求出一个节点要成功发送一个包所消耗的平均能量：

      (5)

将(1)中的z看成单位延迟因子，同时令NE_t=NE_cs=1，可以得到两次成功发送之间的平均时间T。因此节点的平均能量效率h_energy y和吞吐量h分别为：

，        (6)

2、能量效率与p值的关系

因为能量效率对无线传感器网络来说至关重要，本文把分析的重点放在能量效率。能量效率是指在单位时间内，消耗在成功发送数据的能量与消耗总能量的比值。令NE_t: NE_cs=5:1，利用2.1节的能量模型，我们分别计算了不同参数（p与M）对能量效率的影响，如图2、图3所示。

图2中N和M分别为包的长度和节点的数目，从图中可以看出p取值的不同对能量效率的影响很大，曲线在某点取得最大值之后，随着p值的继续增大，由于冲突的最大，能量效率曲线急剧下降。图3是能量效率随着节点数目变化的曲线，此时p＝1/2M。从图中可以看出，随着节点数目的增加，冲突急剧增大，能量效率出现明显恶化的趋势。

关于发送概率p的测量，我们采用与文献^[1]中一样的方法，节点记录从开始发送数据到成功发送过程中经历的所有竞争窗口并计算出竞争窗口的均值。其中E[W]为竞争窗口的均值，由节点经历的竞争窗口大小决定。

                                 (7)

该帖子于2008-5-9 11:47:41被 在那里 编辑过

三、状态检测与竞争节点个数的自适应优化机制（ABM）

本文提出了一种状态检测与竞争节点个数的自适应优化机制，这种机制基本沿用现有的CSMA/CA的DCF机制，不同的是，当节点个数发生变化或者负载增加引起冲突的增加时，对系统参数进行动态的调整，从而有效地改善了原有协议的整体性能。

1、原理与方法

式（7）E[W]为竞争窗口的均值，由节点经历的竞争窗口大小决定，E[W]越大，p越小。由（3）知道，节点成功发送一个包的概率由p决定，假设E[W]＝k时，节点经历了i次冲突成功发送了一个包的概率是P_i。也就是说，一个节点不管经历多少次冲突，只要E[W]＝k，节点成功发送数据的概率都为P_i。我们知道在无线网络中，节点采用的最小竞争窗口对竞争冲突的次数至关重要，较大的最小竞争窗口会带来较小的竞争冲突，竞争冲突是无线网络中能量消耗的重要原因。

从图2、图3及其（3）可以看到竞争节点M的增加会带来冲突的增加，引起p的改变。同时增加负载G也会带来冲突的增加，改变p（参见3.2节）。因此，E[W]的变动反应了网络状况的改变，我们可以调整节点的最小竞争窗口，使i达到最小值，用较少的冲突次数达到同样的E[W]，提高节点能量效率。

2、工作流程

基于上节中性能模型的分析,本文考虑以系统能量效率的优化作为最小竞争窗口调整的主要依据，考虑到竞争节点数目对能量效率的影响，我们对节点数M进行了估计，最后根据计算结果动态的调整系统的最小竞争窗口。

具体过程如下：

（1）节点计算出上次成功发送数据整个过程中竞争窗口的均值E[W]；

（2）节点根据记录的整个传输过程中的空闲时隙（idle slots）Total_Idle估算出竞争节点M的数目；

（3）通过E[W]和Total_Idle计算出最优化的最小竞争窗口CWmin，节点更新自己的CWmin，并相应地调整CWmax(等于2^mCWmin，m是最大回退阶次)。

3、参数检测的方法

在不考虑数据帧因连续多次碰撞被丢弃时，冲突概率e与最小竞争窗口有如下关系：

        (8)

从（7）式求出p后，代入（8）便可求出最优的最小竞争窗口CWmin。这样，根据不同的竞争节点和负载，我们可以通过优化最小竞争窗口CWmin来获得最优的系统能量效率。

该帖子于2008-5-9 11:48:35被 在那里 编辑过

关于竞争终端M的测量，我们采用与文献^[1]中一样的方法：

，

Total_Idle=(E[N_c+1])E[Idle]                     (9)

其中，E[N_C]表示一个数据帧被成功发送前的平均碰撞次数，Total Idle是整个传输过程中平均空闲时隙（idle slots）数目，E[Idle]是每一次尝试发送包过程中经历的空闲时隙数。式(9)中的所有参数可以在文献[1]中找到。E[Idle]和负载G的关系为：

，  g= (10)

其中a是IEEE 802.11定义的一个时隙（slot time）的长度。

由（3）、（9）和（10）式可以看出，冲突概率e随着负载G的增大而增加，最终导致冲突的增加。值得一提的是，通过（9）和（10）可以得出负载的增大引起竞争节点的增加的结论，但实际上竞争节点并没有实质上的改变，这种关系是虚拟的，但是通过这种虚拟的关系，我们可以把负载的变化以竞争节点的改变形式反应出来。

四、ABM机制的仿真

本文采用事件驱动随机仿真的方法进行仿真，采用DSSS物理层（最小竞争窗口为32个时隙），系统达到饱和状态，并假定是理想信道，且不存在隐藏终端。

图4表示在E[CW]与空闲时隙（Total_Idle）不同的情况下，节点采用的最小竞争窗口。由图4可知ABM最小竞争窗口的选择明显比标准算法合理。比如在E[CW]＝199，Total_Idle＝9时，采用标准算法的CWmin＝32，要经过4次冲突才能成功发送数据，而采用ABM机制时CWmin＝178，几乎没有冲突。从图4我们还看到，在E[CW]取值较大，Total_Idle取值较小的区域CWmin的取值也很小，甚至小于E[CW]，此时网络的状况较好，负载不大，用较小的CWmin也能够获得很好的能量效率，这说明ABM机制能够对网络的实际状况做出正确的判断，合理的调整系统参数，减少了系统的冲突。

图5表示在E[CW]与空闲时隙（Total_Idle）不同的情况下，采用ABM机制节点的能量效率。把图5和图2对比可知，采用ABM机制节点的能量效率明显比标准算法高，最高达到了0.67。同时随着E[CW]的增大，能量效率的恶化也是比较显著的，这是因为在E[CW]比较大的情况下，虽然冲突次数不多，但是空闲监听的时间变长，消耗了系统中的大部分能量。

该帖子于2008-5-9 11:50:00被 在那里 编辑过

五、结论和进一步工作

本文提出了一种状态检测与竞争节点个数的自适应优化机制——ABM，同时引入了信号流图模型这种新的方法来建立能量模型。