多信道无线传感器网络容量分析模型研究.doc

第11期王明飞等：多信道无线传感器网络容量分析模型研究61多信道无线传感器网络容量分析模型研究王明飞1,3，慈林林1,2，詹平2，徐勇军3(1. 北京理工大学 计算机科学技术学院，北京 100081；2. 北京信息高技术研究所，北京 100085；3. 中国科学院 计算技术研究所，北京 100190)摘 要：利用理想的数据包流水作业调度方案建立了单用户多信道网络的路径容量分析模型；基于多信道无线网络资源竞争的本质，构建了节点竞争域的资源竞争约束模型，进而利用数学规划建立了多用户多信道网络的容量分析模型，并给出了模型的集中式和分布式求解方法与应用。仿真结果表明，模型可以准确地描述多信道无线传感器网络中的路径容量、网络容量以及数据流的竞争关系。模型建立复杂度低，对网络部署和协议设计具有一定的指导意义。关键词：无线传感器网络；多信道；容量模型；流水作业；数学规划中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)11-0050-12Study on capacity analytical model for multi-channel wireless sensor networksWANG Ming-fei1,3, CI Lin-lin1,2, ZHAN Ping2, XU Yong-jun3(1. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081, China;2. Beijing Institute of Information Technology, Beijing 100085, China;3. Institute of Computing Technology, Chinese Academy of Science, Beijing 100190, China)Abstract: An ideal packets pipeline operation scheme was used to set up the path-oriented capacity analytical model in single user multi-channel network. Then, through analyzing the essence of resource competition in multi-channel networks, the resource constraint model of node contention domain was constructed. Furthermore, the network capacity analytical model in multi-user multi-channel network was set up based on mathematical programming. The centralized and distributed computing methods and applications are studied. The model can describe the path capacity, the network capacity, and the contention relation of the flows in multi-hop multi-channel network. The model is simple, and it can direct the network deployment and the design of network protocols.Key words: wireless sensor networks; multi-channel; capacity model; pipeline operation; mathematical programming1 引言收稿日期：2008-06-10；修回日期：2008-10-28基金项目：国家部委预研基金资助项目（513160303）；国家部委预研重点基金资助项目（9140A16020106DZ2501）；国家高技术研究发展计划（“863”计划）基金资助项目（2006AA01Z223、2006AA01Z225）；国家自然科学基金资助项目（60772070）Foundation Items: The National Ministry Advance Research Program of China (513160303)；The National Ministry Advance Research Key Foundation of China (9140A16020106DZ2501)； The National High Technology Research and Development Program of China (863 Program) (2006AA01Z223, 2006AA01Z225); The National Natural Science Foundation of China (NSFC) (60772070)无线传感器网络1（WSN，wireless sensor network）在突发事件监测、远程监控、环境感知等许多领域具有重要的科研价值和广阔的应用前景。多信道无线传感器网络利用互不重叠信道的隔离特性，支持在多个信道上并行传输数据，从而提高了吞吐量，减少了网络时延，并节省了能量。多信道无线传感器网络的容量不仅与无线链路的物理速率有关，还受到许多因素的影响，如网络拓扑、数据流的分布、数据流的发送速率、信道的数目与分配等。在理论上弄清网络容量与这些因素的关系可以更好地指导网络开发。目前，对无线网络容量的研究多是针对单信道网络环境的，对多信道网络特别是多信道无线传感器网络容量的研究比较匮乏。本文以多信道无线传感器网络的多跳传输路径为研究对象，利用理想的数据包流水作业调度方案建立单用户多信道网络的路径容量分析模型；基于多信道网络资源竞争的本质，构建节点竞争域的资源竞争约束模型，进而利用数学规划建立多用户多信道网络的容量分析模型，并研究模型的集中式和分布式求解方法与应用；最后利用仿真实验验证模型的正确性。2 相关工作当前的网络容量分析方法可分为三类。基于网络的容量分析方法。以Gupta P等2为代表，以网络结构为研究对象，利用协议模型和物理模型对节点之间的干扰行为建模，重点研究给定无线网络的整体容量的上/下界。文献2对无线ad hoc网络容量进行渐近性分析，奠定了无线网络容量分析的理论基础。在其基础上，文献3研究了节点的移动特性对网络容量的影响，文献4研究了将基础设施加入无线ad hoc网络对网络容量的影响，文献5研究了智能天线技术对无线网络容量的影响，文献6研究了多信道多收发器网络容量问题，文献7综述了针对无线传感器网络的容量研究成果。这些文献从宏观的角度来分析网络容量，没有给出精确的表达式，也没有考虑底层协议对网络容量的影响。基于节点的容量分析方法。以Bianchi G等 8为代表，以节点为研究对象，利用二维Markov链对MAC层协议的传输状态进行建模，可给出节点吞吐量的解析表达式。文献8利用二维Markov链模型对基于CSMA/CA机制的无线网络在饱和信道条件下的吞吐量进行了研究，通过对指数回退时间建模，得到了网络的归一化吞吐量。文献9考虑了指数退避机制，建立了CSMA/CA网络的Markov链模型。文献10考虑了分组最大重传次数对Markov链模型进行了改进。文献11研究了网络中存在隐藏终端问题的多跳网络的容量。文献12考虑了多跳网络中节点在成功发送RTS后仍然可能发送DATA失败的情况，提出了一个四维Markov链模型。文献13针对非饱和条件下的IEEE 802.11 DCF网络，推导得到了吞吐量与网络非饱和程度之间的定量数学表达式。文献14针对无线传感器网络的吞吐量进行理论分析，提出了线性网络吞吐量的计算模型。这些文献针对协议细节进行研究，获得的解析表达式复杂，应用场合受很大限制。基于路径的容量分析方法。以刘永强等15, 16为代表，以源节点到宿节点的多跳传输路径为研究对象，先求得路径容量的表达式，然后研究路径容量、网络容量与路径跳数、网络负载等因素的关系。文献15基于流水排队策略，提出了无线多跳网络路径容量分析模型。Kelly等17, 18基于经济学中的市场交易原理提出了一种基于价格（price）的资源分配方法，给出了有线网络中用优化理论解决资源分配问题的基本框架。文献19在Kelly基本框架的基础上，提出了适合于无线多跳网络的基于团（clique）的资源优化模型，但模型中没有对干扰范围和传输范围不等，两点间传输采用多路径等复杂情况进行深入研究。文献16针对无线mesh网络的特点，提出了基于极大链路干扰集的约束表示方法，然后在Kelly基本框架的基础上，建立了网络带宽优化分配模型。这种容量分析方法获得的模型计算比较简单，但是这些文献仅研究了单信道环境下的网络容量，没有对多信道环境下的网络容量进行分析。在实际应用中，单信道网络受网络部署环境和无线干扰范围影响较大，并且很难找到合适的多路径网络拓扑，应用范围受到限制。而由于信道隔离特性，多信道网络的无线干扰影响较小，更易于实现流水作业的工作方式。因此本文采用基于路径的容量分析方法来研究多信道无线传感器网络容量问题。3 容量分析模型的基本思想3.1 模型的工作环境不失一般性，对模型的工作环境做如下假设。1) 每个节点配备单个半双工收发器，收发器可以在多个信道间切换工作，但在某一时刻，收发器只能工作于某一个信道上。2) 多个通信信道之间互相不重叠，即不同信道上的信号互不干扰。3) 通信信道是理想的，即不考虑噪声干扰、链路误码的影响。4) 节点在网络中均匀部署，且在数据包传输过程中不发生移动。5) 数据包仅在源节点产生，路径上的中间节点不产生数据包，只转发数据包。6) 数据包数量远大于传输路径的长度（跳数）。7) 网络可利用信道数量充足。模型中所用符号及说明参见表1。表1模型符号符号定义符号定义EP载荷平均长度T时钟节拍Np路径长度（跳数）Nlp，Nsp长、短路径长度单路径吞吐量单路径容量多路径长度差为偶数时的吞吐量多路径长度差为偶数时的容量多路径长度差为奇数时的吞吐量多路径长度差为奇数时的容量3.2 模型的基本思想因为可利用信道数量充足，网络可以为每个节点分配一个缺省信道。要建立通信时，发送节点切换到接收节点的缺省信道上与其建立通信。通信双方节点所采用的信道与其余节点工作的信道互不重叠，因而，该节点对的通信不会与其余节点的通信相互干扰，从而提升网络的性能。首先建立单用户情况下的多信道网络的路径容量模型。以端到端的多跳传输路径为研究对象，将数据包由源节点到宿节点的传输时间分割成一个个时钟节拍Tsuc，Tsuc为节点间成功发送一个数据包所用的平均时间，然后根据网络拓扑和数据流设计理想的数据包流水作业调度方案，分析数据包到达的平均周期，从而获得多信道无线传感器网络路径容量。然后建立多用户情况下的多信道网络容量模型。以多个用户路径构成的整个网络为研究对象，基于多信道无线网络资源竞争的本质，利用数学模型构建基于节点竞争域的资源竞争约束关系，然后在Kelly资源分配基本框架的基础上，建立多信道网络容量模型。进一步地，利用网络容量模型来研究如何合理配置网络资源以优化网络性能。4 单用户分析模型4.1 单路径容量分析模型定理1 多信道无线多跳网络中，单路径情况下的路径容量为证明 单路径情况下，采用多信道技术的无线多跳网络理想的数据包流水作业调度方案如图1所示。图1 单路径网络的理想数据包调度方案在时间1T，源节点S切换到节点1的缺省信道CH1上向节点1发送数据包Pkt1。在时间2T，节点1流水作业切换到节点2的缺省信道CH2上向节点2转发数据包Pkt1。由于节点仅配备单个半双工收发器，节点1不能同时处于发送和接收状态，源节点S也就不能在时间2T向节点1发送数据包。在时间3T，节点2流水作业切换到节点3的缺省信道CH3上向节点3转发数据包Pkt1。同时，源节点S可以在节点1的缺省信道CH1上继续向节点1发送数据包Pkt2。由于工作在不同的信道上，两对通信可以同时进行。依此方法，源节点每隔一个时钟节拍T发送一个数据包，中间节点流水作业从上游节点接收到数据包后，在下一时钟节拍T向下游节点转发该数据包。假设源节点S每隔一个时钟节拍T发送一个数据包，共向宿节点D发送n个数据包。理想信道中数据包没有因噪声干扰、链路误码的影响而丢弃，按照理想的数据包流水作业调度方案，宿节点D可以每隔一个时钟节拍T接收到一个数据包，从而接收到所有的n个数据包。那么，路径最大吞吐量为又，故路径容量为。证毕。4.2 多路径容量分析模型采用多路径传输技术可以解除路径上中间节点的半双工工作方式的制约，进一步增加多信道网络的空间复用度，提高端到端的数据吞吐量。4.2.1 路径长度之差为偶数的分析模型定理2 多信道无线多跳网络中，在源节点和宿节点间给定两条节点不相交路径，当两条路径长度之差为偶数时，端到端的数据最大吞吐量为并且，再增加两点间路径的数目不会增加两点间的最大吞吐量。证明 首先，证明两条路径长度相等的情况。不失一般性，以两条路径均为5跳的网络为例，理想的流水作业调度方案如图2所示。图2 路径长度相等的多路径网络理想数据包调度方案类似于定理1的分析方法，可以得到路径的吞吐量为又，故多路径容量为。同理，可以证明两条路径长度之差为2、4、6偶数的情况，结论同上。将两条路径的传输抽象为一个管道，源节点S和寄存器节点D都是在每个时钟节拍T向管道注入数据包，源节点S和宿节点D均分别达到了最大发送能力和最大接收能力，因此，再增加两点间路径的数目不会增加两点间的最大吞吐量。证毕。值得指出，源节点S发送的数据包经两条长度不一致的路径到达宿节点D时会出现数据包乱序，数据包乱序并不会影响端到端的数据吞吐量。从定理2可以看出，当两条路径长度之差为偶数时，在源节点和宿节点间端到端的数据吞吐量可以达到单跳传输时点对点的数据吞吐量，达到理想状态。然而，当两条路径长度之差为奇数时，流水作业不再如此完美。4.2.2 路径长度之差为奇数的分析模型假设两条路径长度之差为奇数，两条路径上的中间节点分别流水作业转发数据包，那么，两条路径上的数据包会在同一个时钟节拍到达宿节点。为避免碰撞，其中一条路径上的数据包必须延缓发送，增加了数据包的传输时延，相应地减少了端到端的吞吐量。本文采用长路径上节点缓存数据包的策略来分析端到端的吞吐量。当两条路径上的数据包同时到达最后一个中间节点时，长路径上数据包主动缓存，避让短路径上数据包，延缓一个时钟节拍后再向宿节点发送。定理3 多信道无线多跳网络中，在源节点和宿节点间给定两条节点不相交路径，当两条路径长度之差为奇数时，端到端的数据吞吐量可以达到证明 假设源节点首先向短路径发送，采用长路径上节点缓存数据包的策略，理想的流水作业调度方案如图3所示。假设两条路径长度之差为m。源节点由短路径开始交替向两条路径发送数据包。两跳路径上的中间节点分别流水作业转发数据包。经Nlp个时钟节拍后，长路径上的首个数据包到达最后一个中间节点，此时，短路径上的第(m+3)/2个数据包也将到达最后一个中间节点。让长路径上数据包主动缓存，延缓一个时钟节拍后再向宿节点发送，以避让短路径上数据包。长路径上的最后一个中间节点在Nlp+1个时钟节拍缓存数据包，在Nlp+2个时钟节拍向宿节点发送数据包。进而，上游节点将延缓一个时钟节拍向该节点发送数据包。依此类推，在Nlp+1个时钟节拍到2Nlp1个时钟节拍，长路径上的中间节点将依次缓存数据包一个时钟节拍。然后，源节点空闲一个时钟节拍，以保证路径上的数据包依次到达宿节点。这样，经过2Nlp个时钟节拍，即2NlpT时间后，多信道网络上的数据包调度过程完成一个周期。图3 路径长度差为奇数的多路径网络理想数据包调度方案将两条路径的传输抽象为一个管道。在这2Nlp个时钟节拍内，源节点有2Nlp1个时钟节拍向管道注入2Nlp1个数据包，并有1个时钟节拍空闲以避免数据包的冲突。按照流水作业调度方案，宿节点也将在路径延迟后，在2Nlp个时钟节拍内从管道中获取2Nlp1个数据包。那么，端到端的数据吞吐量可以达到同理，可以分析源节点首先向长路径发送数据包的情况。经Nlp个时钟节拍后，长路径上的首个数据包到达最后一个中间节点时，短路径上的第(m+1)/2个数据包也将到达最后一个中间节点。为避免碰撞，采取长路径上节点缓存数据包的策略。进一步地分析，该情况与源节点首先向短路径发送数据包的情况一致，结论同上。 证毕。可以利用图论深入分析路径长度差为奇数时网络性能下降与数据流所经路径构成非偶图（non-bipartite graph）有关。在非偶图中，不能将任意一条边的两个顶点划分为两个不相交的集合。这样，路径上的节点不能交替处于收发两种状态，因而不能完美实现流水作业，造成网络性能下降。5 多用户分析模型多信道无线传感器网络与单信道环境下的无线网络不同，由于多信道技术的信道隔离性质，制约无线网络性能的因素不再是单信道条件下的无线链路干扰问题，而是节点所配备的单收发器的半双工工作方式。多信道无线网络资源竞争的本质是流经同一节点的输入输出数据流竞争该节点的单个无线收发器资源。本节构建基于节点竞争域的资源竞争约束模型，进而利用数学规划建立多用户多信道无线传感器网络的容量分析模型。5.1 多信道无线网络抽象模型多信道无线传感器网络可抽象为一个无向图G=(N, L)，其中，N为网络中节点的集合，L为网络中通信链路的集合。网络的链路l定义为lij=(Ni, Nj) L，即l所关联的两个节点间存在一条通信链路。定义1 DL且D满足1) ljk=(Nj, Nk)D，(Ni=Nj)(Ni=Nk)2) lst=(Ns, Nt) D，(NiNs)(NiNt)则称D为网络G中节点Ni的节点竞争域（node contention domain）。可以看出，节点竞争域D是网络G中与节点Ni相关联的通信链路的集合。设:D2L表示网络中所有节点竞争域的集合。设网络中一对通信的源宿节点对表示一个用户的数据流，数据流的方向总是由源节点Ns流向宿节点Nd。设F为网络中所有用户数据流的集合，定义向量X=(xf, fF)，xf为用户数据流f的端到端吞吐量所占链路实际容量的比例因子。定义路径为由源节点到宿节点的通信链路的顺序序列。设R为网络中所有用户数据流的路径的集合。定义0-1矩阵A=(afr, fF, rR)描述用户数据流与路径之间的关系，如果数据流f使用路径r进行传输，则afr=1；否则，afr=0。定义向量Y=(yr, rR)，yr为路径r所传输数据的吞吐量所占链路实际容量的比例因子。一个用户的数据流的端到端吞吐量为并行传输的所有路径的端到端吞吐量之和。因此，用户数据流f的吞吐量所占链路容量的比例因子可表示为xf =(afryr)用矩阵表示为X = AY (1)5.2 多信道网络资源约束分析模型基于节点竞争域的网络资源约束分析过程分为三个步骤：首先分析同一个节点竞争域中链路之间的竞争约束；然后分析多个用户数据流在同一传输链路上的竞争约束；最后，将两类约束合二为一，建立基于节点竞争域的资源约束模型。5.2.1 节点竞争域内链路竞争约束分析模型设节点的实际容量即节点的实际收发速率为cn，nN。假设在无干扰情况下的无线网络数据链路的实际容量为cl，lL。易知，链路的实际容量等于节点的实际容量，即cl = cn。多信道无线网络中，流经同一节点的输入输出数据链路竞争该节点的单个收发器资源。因而，节点竞争域内的所有链路的实际吞吐量之和受限制于节点的实际容量。因此，节点竞争域内的链路吞吐量约束可表示为Thr(l)cn，Thr(l)cl将约束条件进行归一化描述。设l为数据链路的带宽比例因子，即流经链路l的实际吞吐量占链路实际容量的比例。那么，节点竞争域内的链路吞吐量约束又可表示为l clcl，即l1由节点竞争域的定义可知，节点数目为n的多信道网络，可以划分为n个节点竞争域。然而，如果网络中某节点的度为1，即与该节点关联的链路仅有1条，不存在竞争问题，则将其从节点竞争域集合中去掉。假设网络可划分为k个节点竞争域，即=D1, D2, , Dk。定义0-1矩阵B=(bDl, D, lL)描述节点竞争域与数据链路之间的关系，如果数据链路在节点竞争域内，即lD，则bDl=1；否则，bDl=0。定义向量=(l, lD)为所有数据链路的带宽比例因子。那么，节点竞争域内的链路吞吐量约束的矩阵表示形式为B1(2)5.2.2 流经同一链路的路径竞争约束分析模型当网络中的某一链路传输来自不同路径的数据包时，不同路径的数据包在同一链路上形成竞争。设yrl, lL, rR为路径r所占链路l实际容量的比例因子，若链路l上传输m条路径的数据流，则在l上的路径吞吐量约束可归一化表示为l路径r的端到端吞吐量应等于路径上的所有链路中瓶颈链路的吞吐量，即路径端到端吞吐量所占链路实际容量的比例因子yr=。因此，m条路径的数据流在链路l上的竞争路径约束为l定义0-1矩阵G=(glr, lL, rR)描述数据链路与路径之间的关系，如果数据链路在路径r的链路序列中，则glr=1；否则，glr=0。因此，流经同一链路的路径的吞吐量约束的矩阵形式为GY(3)5.2.3 竞争约束分析模型的整合可将式(2)、式(3)整合为如下不等式约束BGY1令矩阵H=BG，则多信道无线多跳网络的竞争约束条件可用矩阵表示为HY1 (4)矩阵H在多信道无线多跳网络中有其实际的意义。H=(hDr, D, rR)表示路径r的链路序列中在节点竞争域D中的链路数目。综合式(1)、式(4)，多信道无线多跳网络的资源竞争约束可用矩阵标准型表示为其中，X和Y为变量矩阵；A和H为参数矩阵。5.3 多用户网络容量分析模型的建立按照Kelly资源分配基本框架，以比例公平模型17为基础，选取效用函数Uf(xf)=log(xf)。多信道无线多跳网络容量分析模型可以描述为如下优化问题的求解。最大化log(xf)约束条件 其中，Y为多信道网络中路径带宽比例因子向量，X为用户数据流的带宽比例因子向量，矩阵A表示用户使用多路径传输的情况，矩阵H表示路径与节点竞争域的关系。可以证明该优化问题在可行域内存在惟一的最优解。设模型的最优解为X*=x1*, x2*, , xn*，则用户数据流f的实际带宽为Wf =xn*cl。cl可通过公式EP/Tsuc求得。5.4 模型的集中式求解与应用用户给定网络拓扑G和链路带宽cl，以及用户数据流F的路由信息R。求解网络容量分析模型可以完成以下功能。1) 为用户提供该网络的无线资源的约束关系；2) 判断用户的带宽需求向量X=x1, x2, xn在当前网络条件下是否可行；3) 获得该网络的最优资源分配向量X*=x1*, x2*, , xn*。5.4.1 求解网络带宽约束确定给定网络的约束条件，需要确定参数矩阵A和H。矩阵A可通过用户输入的数据流F和数据流使用的路由信息R确定。矩阵H由H=BG求得。B由给定网络的节点竞争域D确定，G可由F和R确定。节点竞争域是与节点相关联的所有链路的集合。给定网络拓扑图G，就可以方便地得到网络的节点竞争域。5.4.2 求解网络带宽需求可行性确定给定网络的约束条件后，判断用户的带宽需求向量X=x1, x2, , xn在当前网络条件下是否可行，可转化为求解下面的优化问题：最大化 约束条件 其中，表示在当前网络约束和用户带宽需求条件下，路径带宽比例因子Y的可扩展系数。设该优化问题的最优解为*，若*1，则X向量可行；若*1，则X向量不可行。5.4.3 求解网络最优带宽分配采用Lagrange乘子法求解优化问题的最优解。该优化问题的Lagrange函数为设X*=x1*, x2*, xn*T为该优化问题的最优解，根据Kuhn-Tucker条件，存在Y*=y1*, y2*, yn*T，*=1*,2*, , n*T，*=1*,2*, , n*T满足如下等式和不等式： (X*, Y*, *, *) = 0；(X*, Y*, *, *)= 0；X* =AY*；HY* 10；* 0；*T (HY* 1) = 0。求解上述等式和不等式组，即可得到上述优化问题的最优解。5.5 模型的分布式求解与应用虽然上面的优化问题可以直接求解，但需要知道全部流的信息，这在实际网络中是不可能实现的。所以需要将求解算法转化成网络可执行的分布式算法。本小节给出网络容量分析模型的分布式求解方法及其在流量控制和路由优化中的应用。5.5.1 多信道网络的流量控制鉴于多路径传输数据流不会与其他数据流的路径相交，从而可以独立计算，本节假设数据流采用单路径传输。因此，5.3节中的容量分析模型可简化为如下最优化问题的求解最大化约束条件 HX 1 0X 0利用优化理论中的原始对偶方法进行分析，则其对应的Lagrange函数为其中，=1, 2, , k为Lagrange乘子，hif为数据流f在节点竞争域i中的链路数。Lagrange函数对应的关于变量的对偶函数为则原始问题对应的对偶问题为：min(D()。设对偶问题的最优解为*，则原始问题的最优解为。其中，表示数据流从源节点到宿节点所经历的所有节点竞争域的价格之和。i*hif表示节点竞争域内的所有链路的价格之和。将这种使用总的价格作为反馈信号的网络模型称为多信道网络的总价（SumNet）模型，如图4所示。总价模型可以反映网络一个整体的信息，可以证明通过这种模型得到的算法达到比例公平。图4 SumNet模型在互联网的拥塞控制体系结构研究中，Wydrowski B等 22提出了一种最大价格（MaxNet）模型，如图5所示。这种模型不是反馈给源端所历经的链路的总价格，而是选择链路中的价格最大的那个值。文献22分析通过选择适当的效用函数，使用MaxNet模型的算法对于一般的源端有不同需求函数的网络可以达到全局的最大最小公平，而且不需要全局信息也无需链路保存每个流的状态。图5 MaxNet模型前面分析已知，多信道网络中流的最大传输速率受流所经历的所有节点中瓶颈节点竞争域的限制，只需要使流经瓶颈节点竞争域的流的总速率不要超过实际容量就可以控制拥塞。因此，本文主要考虑网络中的瓶颈节点的竞争域，采用所有节点竞争域中最大的价格作为反馈信号的网络模型，称为多信道网络的最大价格模型。则数据流f对应的最优解为该表达式具有实际意义：hif为数据流f在节点竞争域中的链路数；i*为节点竞争域中数据流的个数；i*hif表示节点竞争域内的所有链路数。为便于表述，并区别于网络拓扑图中链路数的概念，本文引入“虚拟链路数”的概念。定义2 虚拟链路数Vi表示流经节点i的所有流在该节点竞争域内的链路数之和。其中，Wf表示流f在提供QoS带宽保证的网络中的QoS权值。Hif表示流f流经节点i的竞争域的链路数。那么，在MaxNet模型中，。下面建立多信道网络的流量控制算法。因为节点在某一时刻只能在竞争域内的某一个链路上工作，需要设定时间窗口统计一段时间内节点的工作状态，包括流经节点的流的数目和相应流在节点竞争域的虚拟链路数。流的标识信息捎带在传输的报文中。实现过程如图6所示，多信道无线传感器网络的流量控制算法如图7所示。图6 MaxNet模型的实现图7 多信道无线传感器网络的流量控制算法5.5.2 多信道网络的路由优化在进行路由选择时应尽量避免将瓶颈节点加入路由，一方面可以避免数据流的最大传输速率受到瓶颈限制，另一方面可以避免影响瓶颈节点已有的通信，加重拥塞。本文将模型中提出的虚拟链路数的概念应用到路由优化工作中，将其作为路由选择时的重要参考依据，从而优化网络的整体性能。网络中每个节点根据网络运行情况实时维护虚拟链路数。用户在建立路由时，根据节点的虚拟链路数可以实时求解选择该节点为路由节点后的最大传输速率，从而根据能否满足带宽需求来决定是否将该节点加入路由。一般网络中，在满足连通性等指标的基础上，可以尽量选择虚拟链路数小的节点加入路由。如果应用到提供QoS保证的网络，可以判断该节点加入路由后能否满足带宽需求。6 模型验证与性能分析本文利用网络仿真软件NS-2.3120来验证模型的正确性。物理层采用DSSS机制，MAC层为在802.11和RDT21协议基础上添加实现的多信道MAC协议，网络层采用静态配置路由，传输层采用UDP协议，应用层为CBR数据流。无线传感器网络中的竞争窗口参数CW通常设为固定值14，本文实验取值为31。由于信道切换时延为某一固定值，并仅跟物理层芯片有关，本文未考虑信道切换时延。通过调整数据包的发送时间间隔来控制流量负载。实验结果为10次实验的平均值。具体实验参数值见表2。表2仿真实验参数参数名称数值参数名称数值Data payload500byteDIFS50sIP header160bitSIFS10sMAC header240bitSlot Time20sPHY header192bit1sRTS368bitCW31CTS320bitCS Delay0ACK320bitData Rate1Mbit/sDTC368bitBasic Rate1Mbit/s流水作业的时钟节拍Tsuc可以由下式给出：Tsuc=TCS+DIFS+TRTS+SIFS+TCTS+SIFS+TDATA+SIFS+TACK+SIFS+TDTC+W其中，TCS为信道切换时延；DIFS和SIFS均为帧间间隔；TRTS、TCTS、TACK、TDTC分别是传输RTS、CTS、ACK、DTC21报文所用的时间；TDATA为传输一个完整的数据帧所用的时间，该数据帧包括物理层头部、链路层头部、网络层头部和有效载荷；W为发送数据包所用的平均等待时间（包括发送前的等待和冲突产生的退避）；为无线信号传播时延。根据模型和仿真实验参数，可以计算时钟节拍Tsuc=6 373s，链路实际容量cl=0.627 7Mbit/s。单用户网络仿真实验分别采用类似图1图3的网络拓扑，在路径长度一定的条件下，调节源节点的发包间隔，使到达宿节点的吞吐量达到最大值。模型计算结果与仿真实验结果分别如图8图10所示。其中，多路径网络实验结果中的两条路径的长度用“”隔开表示。定义误差=|V理论V实测|/V实测，误差曲线分别如图1113所示。可以看出，路径容量分析模型计算得到的理论容量值在不同的路径数和路径长度时，都比较准确地反映了实际容量的变化趋势和上边界。单路径网络容量模型的误差在3%以内，多路径网络容量模型的误差在9%以内。多路径网络容量模型的误差大于单路径网络容量模型的误差。单路径网络的瓶颈节点在路径上的中间节点，可以利用源节点增加数据包发送速率使路径上传输的数据包尽可能实现流水作业，源节点发送速率过大造成的丢包并不会影响整条路径的传输时间。而多路径网络的瓶颈节点就是源节点，源节点增加发送速率造成的丢包会浪费路径的传输时间，造成性能下降。误差随路径长度增加而增加。这是因为路径越长，数据包能在整条路径上完整实现流水作业传输的概率越小。多用户网络仿真实验采用图14所示的网络拓扑仿真。图中有两个用户数据流，流f1的源节点为S1，宿节点为D1，所采用的路径为r1=(S1, 1), (1, 2), (2, D1)；流f2的源节点为S2，宿节点为D2，所采用的路径为r2=(S2, 1), (1, 2), (2, 3), (3, 4), (4, D2)。利用模型可以计算得到两条流的最优发送速率均为cl/4，网络中两流之和为cl/2。仿真实验流f1、流f2、两流之和的最大吞吐量分别为0.308 4Mbit/s、0.154 23Mbit/s、0.154 21Mbit/s，误差均约为1.76%。可见，多用户网络容量模型也具有较高的准确度。仿真实验分析多信道网络中数据流负载对网络吞吐量的影响关系。单路径网络、多路径网络以及多用户网络的仿真实验结果分别如图17图19所示。可见，网络的吞吐量开始随着数据流负载的增加而增加，当达到最大值后，单路径网络的吞吐量保持不变，但可以验证重负载时数据包时延性能会明显下降。多路径网络的吞吐量达到最大值后随负载的增加而减小。这也说明了流量控制的必要性。仿真实验测试多信道网络流量控制算法的性能。针对多用户网络分别采用流量控制算法和不采用流量控制算法进行仿真实验，获得数据包的传输时延。限于篇幅，仅给出流1的仿真实验结果分别如图15、16所示，流2的仿真实验结果与流1基本相同。可见，采用流量控制算法的数据包传输时延性能明显优于不采用流量控制算法的数据包传输时延性能。利用网络容量分析模型可以得到用户最佳的发送速率，从而保证网络整体的性能。图8 单路径网络容量模型与实验结果对比图9 长度差为偶数的多路径网络模型与实验结果对比图10 长度差为奇数的多路径网络模型与实验结果对比图11 单路径网络模型的误差曲线图12 长度差为偶数的多路径网络模型误差曲线图13 长度差为奇数的多路径网络模型误差曲线图14 多用户网络仿真实验拓扑图15 采用流控算法的包传输时延分布图16 未采用流控算法的包传输时延分布图17 单路径网络吞吐量与负载的关系图18 多路径网络吞吐量与负载的关系图19 多用户网络吞吐量与负载的关系7 结束语本文构建的容量分析模型可以准确地描述多信道无线传感器网络容量的上边界，模型计算简单，对网络部署和协议设计具有一定的指导意义。本文的假设对模型的实际应用影响较小。假设1)、2)、3)、6)是在实际网络应用中较容易满足的；假设4)中节点的移动只要不离开通信对方节点的传输范围，就不影响网络的性能；假设5)中路径上的中间节点也产生数据包的情况可以按照多用户网络容量模型进行分析。假设7)中网络信道数量充足只需要满足在两跳干扰范围内的活跃节点使用的信道不重复即可，两跳干扰范围外的节点可以复用信道。参考文献：1/EB/OL. 2008.2GUPTA P, KUMAR P. The capacity of wireless networksJ. Journal of IEEE Trans on Information Theory, 2000,46(2):388-404.3GROSSGLAUSER M, TSE D N C. Mobility increases the capacity of ad hoc wireless networksJ. IEEE/ACM Trans on Networking, 2002,10(4): 477-486.4KOZAT U C, TASSIULAS L. Throughput capacity of random ad hoc networks with infrastructure supportA. ACM Annual International Conference on Mobile Computing and Networking (MobiCom03)C. San Diego, CA, 2003.55-65.5SU Y, YONG P, SHIVKUMAR K. On the capacity improvement of ad hoc wireless networks using directional antennasA. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc03)C. Maryland, 2003. 108-116.6KYASANUR P, VAIDYA N. Capacity of multi-channel wireless networks: Impact of number of channels and interfacesA. Proceedings of the ACM MobicomC. Cologne, 2005. 43-57.7刘雨, 望育梅, 邓辉. 无线传感器网络的容量研究综述J. 计算机科学, 2006,33(4):39-41.LIU Y, WANG Y M, DENG H. The capacity problem of wireless sensor networksJ. Computer Sciences, 2006,33(4):39-41.8BIANCHI G. Performance analysis of the IEEE 802.11 distributed coordination functionJ. IEEE Journal on Selected Areas in Communications, 2000,18(3):535-547.9ZIOUVA E, ANTONAKOPOULOS T. CSMA/CA performance under high traffic conditions: throughput and delay analysisJ. Journal of Computer Communications, 2002,25(3):313-321.10WU H, PENG Y, LONG K, et al. Performance of reliable transport protocol over IEEE 802.11 wireless LAN: analysis and enhancementA. Proceedings of IEEE INFOCOMC. Nevada, USA, 2002.599-607.11HOU T C, TSAO L F. Analyzing the throughput of IEEE 802.11 DCF scheme with hidden nodesA. Proc of the IEEE Vehicular Technology ConfC. Florida, 2003. 2870-2874.12肖永康. 无线ad hoc网络中MAC协议和TCP的性能研究D. 清华大学, 2004.XIAO Y K. Performance Research on th