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

第２９卷第１１期　通信学报　Ｖ　１．２９　Ｎｏ．１１　２００８年１１月　Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｎｏｖｅｍｂｅｒ　２００８　多信道无线传感器网络容量分析模型研究　王明飞１，３慈林林１，２詹平　，徐勇军。　（１北京理工大学计算机科学技术学院，北京１０００８１；　２北京信息高技术研究所，北京１０００８５；３．中国科学院计算技术研究所，北京１００１９０）　摘要：利用理想的数据包流水作业调度方案建立了单用户多信道网络的路径容量分析模型；基于多信道无线网络资　源竞争的本质，构建了节点竞争域的资源竞争约束模型，进而利用数学规划建立了多用户多信道网络的容量分析模型，　并给出了模型的集中式和分布式求解方法与应用。仿真结果表明，模型可以准确地描述多信道无线传感器网络中的路　径容量、网络容量以及数据流的竞争关系。模型建立复杂度低，对网络部署和协议设计具有一定的指导意义。　关键词：无线传感器网络；多信道；容量模型；流水作业；数学规划　中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１０００—４３６Ｘ（２００８）１１—００５０—１２　Ｓｔｕｄｙ　０ｎ　ｃａｐａｃｉｔｙ　ａｎａｌｙｔｉｃａｌ　ｍｏｄｅｌ　ｆｏｒ　ｌ・●　ｌ　ｌ　－　ｌ　Ｊ　■　ｍｕｌｔｉ－ｃｎａｎｎｅｌ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔＷ０ｒＫＳ　ＷＡＮＧ　Ｍｉｎｇ—ｆｅｉ　，ＣＩ　Ｌｉｎ．１ｉｎ　Ｉ＿，ＺＨＡＮ　Ｐｉｎｇ　，ＸＵ　Ｙｏｎｇｏｊｕｎ　（１．Ｓｃｈｏｏｌ　ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，ＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，ＢｅＯｉｎｇ１０００８１，Ｃｈｉｎａ；　２．Ｂｅｉｊｉｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ　１０００８５，Ｃｈｉｎａ；　３．Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ　１００１９０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｎ　ｉｄｅａｌ　ｐａｃｋｅｔｓ　ｐｉｐｅｌｉｎｅ　ｏｐｅｒａｔｉｏｎ　ｓｃｈｅｍｅ　ｗａｓ　ｕｓｅｄ　ｔｏ　ｓｅｔ　ｕｐ　ｔｈｅ　ｐａｔｈ—ｏｒｉｅｎｔｅｄ　ｃａｐａｃｉｔｙ　ａｎａｌｙｔｉｃａｌ　ｍｏｄｅｌ　ｉｎ　ｓｉｎｇｌｅ　ｕｓｅｒ　ｍｕｌｔｉ—ｃｈａｎｎｅｌ　ｎｅｔｗｏｒｋ．Ｔｈｅｎ，ｔｈｒｏｕｇｈ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｅｓｓｅｎｃｅ　ｏｆ　ｒｅｓｏｕｒｃｅ　ｃｏｍｐｅｔｉｔｉｏｎ　ｉｎ　ｍｕｌｉｔ—ｃｈａｎｎｅｌ　ｎｅｔ一ｗｏｒｋｓ，ｔｈｅ　ｒｅｓｏｕｒｃｅ　ｃｏｎｓｔｒａｉｎｔ　ｍｏｄｅｌ　ｏｆ　ｎｏｄｅ　ｃｏｎｔｅｎｔｉｏｎ　ｄｏｍａｉｎ　ｗａｓ　ｃｏｎｓｔｒｕｃｔｅｄ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｅ　ｎｅｔｗｏｒｋ　ｃａｐａｃｉｔｙ　ｎａａｌｙｔｉｃａｌ　ｍｏｄｅｌ　ｉｎ　ｍ￣ｌｔｉ—ｕｓｅｒ　ｍｕｌｔｉ—ｃｈａｎｎｅｌ　ｎｅｔｗｏｒｋ　ｗａｓ　ｓｅｔ　ｕｐ　ｂａｓｅｄ　ｏｎ　ｍａｔｈｅｍａｔｉｃａｌ　ｐｒｏｇｒａｍｍｉｎｇ．Ｔｈｅ　ｃｅｎｔｒａｌｉｚｅｄ　ｎａｄ　ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｍｐｕｔｉｎｇ　ｍｅｔｈｏｄｓ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎｓ　ａｒｅ　ｓｔｕｄｉｅｄ．Ｔｈｅ　ｍｏｄｅｌ　Ｃａｌｌ　ｄｅｓｃｒｉｂｅ　ｔｈｅ　ｐａｔｈ　ｃａｐａｃｉｔｙ，ｔｈｅ　ｎｅｔｗｏｒｋ　ｃａｐａｃｉｔｙ，ａｎｄ　ｈｔｅ　ｃｏｎｔｅｎｔｉｏｎ　ｒｅｌａｔｉｏｎ　ｏｆ　ｔｈｅ　ｆｌｏｗｓ　ｉｎ　ｍｕｌｉｔ—ｈｏｐ　ｍｕｌｔｉ—ｃｈａｎｎｅｌ　ｎｅｔｗｏｒｋ．Ｔｈｅ　ｍｏｄｅｌ　ｉｓ　ｓｉｍｐｌｅ，ａｎｄ　ｉｔ　ｃａｎ　ｄｉ—　ｒｅｃｔ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｄｅｐｌｏｙｍｅｎｔ　ａｎｄ　ｔｈｅ　ｄｅｓｉｇｎ　ｏｆ　ｎｅｔｗｏｒｋ　ｐｒｏｔｏｃｏｌｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ；ｍｕｌｉｔ—ｃｈａｎｎｅｌ；ｃａｐａｃｉｔｙ　ｍｏｄｅｌ；ｐｉｐｅｌｉｎｅ　ｏｐｅｒａｔｉｏｎ；ｍａｔｈｅｍａｔｉｃａｌ　ｐｒｏｇｒａｍｍｉｎｇ　１　引言　ｎｅｔｗｏｒｋ）在突发事件监测、远程监控、环境感知等　许多领域具有重要的科研价值和广阔的应用前景。　无线传感器网络　１（ＷＳＮ，ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　多信道无线传感器网络利用互不重叠信道的隔离　收稿日期：２００８—０６—１０；修回日期：２００８．１０—２８　基金项目：国家部委预研基金资助项目（５１３１６０３０３）；国家部委预研重点基金资助项目（９１４０Ａ１６０２０１０６ＤＺ２５０１）：国家高　技术研究发展计划（“８６３”计划）基金资助项目（２００６ＡＡ０１Ｚ２２３、２００６ＡＡ０１Ｚ２２５）；国家自然科学基金资助项目（６０７７２０７０）　Ｆｏｕｎｄａｔｉｏｎ　Ｉｔｅｍｓ：Ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｍｉｎｉｓｔｒｙ　Ａｄｖａｎｃｅ　Ｒｅｓｅａｒｃｈ　Ｐｒｏｇｒａｍ　ｏｆ　Ｃｈｉｎａ（５１３１６０３０３）Ｉ　Ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｍｉｎｉｓｔｒｙ　Ａｄｖａｎｃｅ　Ｒｅ—　ｓｅａｒｃｈ　Ｋｅｙ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（９１４０Ａ１６０２０１０６ＤＺ２５０１）；Ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｈｉｇｈ　Ｔｅｃｈｎｏｌｏｇｙ　Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｄｅｖｅｌｏｐｍｅｎｔ　Ｐｒｏｇｒａｍ　ｏｆ　Ｃｈｉｎａ（８６３　ｒＰｏｇｒａｍ）（２００６ＡＡ０１Ｚ２２３，２００６ＡＡ０１Ｚ２２５）；ｈＴｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｒｕａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ（ＮＳＦＣ）（６０７７２０７０）　第１１期　王明飞等：多信道无线传感器网络容量分析模型研究　・５１・　特性，支持在多个信道上并行传输数据，从而提高　Ｍａｒｋｏｖ链模型进行了改进。文献［１１］研究了网络中　了吞吐量，减少了网络时延，并节省了能量。多信　存在隐藏终端问题的多跳网络的容量。文献［１２］考　道无线传感器网络的容量不仅与无线链路的物理　虑了多跳网络中节点在成功发送ＲＴＳ后仍然可能　速率有关，还受到许多因素的影响，如网络拓扑、　发送ＤＡＴＡ失败的情况，提出了一个四维Ｍａｒｋｏｖ　数据流的分布、数据流的发送速率、信道的数目与　链模型。文献［１３］针对非饱和条件下的ＩＥＥＥ　分配等。在理论上弄清网络容量与这些因素的关系　８０２．１１　ＤＣＦ网络，推导得到了吞吐量与网络非饱　可以更好地指导网络开发。　和程度之间的定量数学表达式。文献『１４］针对无　目前，对无线网络容量的研究多是针对单信道　线传感器网络的吞吐量进行理论分析，提出了线　网络环境的，对多信道网络特别是多信道无线传感　性网络吞吐量的计算模型。这些文献针对协议细　器网络容量的研究比较匮乏。本文以多信道无线传　节进行研究，获得的解析表达式复杂，应用场合　感器网络的多跳传输路径为研究对象，利用理想的　受很大限制。　数据包流水作业调度方案建立单用户多信道网络　基于路径的容量分析方法。以刘永强等【ｌ　】　的路径容量分析模型；基于多信道网络资源竞争的　为代表，以源节点到宿节点的多跳传输路径为研究　本质，构建节点竞争域的资源竞争约束模型，进而　对象，先求得路径容量的表达式，然后研究路径容　利用数学规划建立多用户多信道网络的容量分析　量、网络容量与路径跳数、网络负载等因素的关系。　模型，并研究模型的集中式和分布式求解方法与应　文献［１５］基于流水排队策略，提出了无线多跳网络　用；最后利用仿真实验验证模型的正确性。　路径容量分析模型。Ｋｅｌｌｙ　７，　】基于经济学中的　２相关工作　市场交易原理提出了一种基于价格（ｐｒｉｃｅ）的资源　分配方法，给出了有线网络中用优化理论解决资源　当前的网络容量分析方法可分为三类。　分配问题的基本框架。文献［１９］在Ｋｅｌｌｙ基本框架的　基于网络的容量分析方法。以Ｇｕｐｔａ　Ｐ等　为　基础上，提出了适合于无线多跳网络的基于团　代表，以网络结构为研究对象，利用协议模型和物　（ｃｌｉｑｕｅ）的资源优化模型，但模型中没有对干扰　理模型对节点之间的干扰行为建模，重点研究给定　范围和传输范围不等，两点间传输采用多路径等复　无线网络的整体容量的上／下界。文献［２】对无线ａｄ　杂情况进行深入研究。文献［１６］针对无线ｍｅｓｈ网络　ｈｏｃ网络容量进行渐近性分析，奠定了无线网络容　的特点，提出了基于极大链路干扰集的约束表示方　量分析的理论基础。在其基础上，文献【３】研究了节　法，然后在Ｋｅｌｌｙ基本框架的基础上，建立了网络　点的移动特性对网络容量的影响，文献［４］研究了将　带宽优化分配模型。这种容量分析方法获得的模型　基础设施加入无线ａｄ　ｈｏｃ网络对网络容量的影响，　计算比较简单，但是这些文献仅研究了单信道环境　文献【５］研究了智能天线技术对无线网络容量的影　下的网络容量，没有对多信道环境下的网络容量进　响，文献［６】研究了多信道多收发器网络容量问题，　行分析。在实际应用中，单信道网络受网络部署环　文献［７】综述了针对无线传感器网络的容量研究成　境和无线干扰范围影响较大，并且很难找到合适的　果。这些文献从宏观的角度来分析网络容量，、没有　多路径网络拓扑，应用范围受到限制。而由于信道　给出精确的表达式，也没有考虑底层协议对网络容　隔离特性，多信道网络的无线干扰影响较小，更易　量的影响。　于实现流水作业的工作方式。因此本文采用基于路　基于节点的容量分析方法。以Ｂｉａｎｃｈｉ　Ｇ等　Ｊ　径的容量分析方法来研究多信道无线传感器网络　为代表，以节点为研究对象，利用二维Ｍａｒｋｏｖ链　容量问题。　对ＭＡＣ层协议的传输状态进行建模，可给出节点　吞吐量的解析表达式。文献［８１Ｎ用二维Ｍａｒｋｏｖ链　３容量分析模型的基本思想　模型对基于ＣＳＭＡ／ＣＡ机制的无线网络在饱和信道　３．１模型的工作环境　条件下的吞吐量进行了研究，通过对指数回退时间　不失一般性，对模型的工作环境做如下假设。　建模，得到了网络的归一化吞吐量。文献［９】考虑了　１）每个节点配备单个半双工收发器，收发器可　指数退避机制，建立了ＣＳＭＡ／ＣＡ网络的Ｍａｒｋｏｖ　以在多个信道间切换工作，但在某一时刻，收发器　链模型。文献【１０】考虑了分组最大重传次数对　只能工作于某一个信道上。　通信学报　第２９卷　２）多个通信信道之间互相不重叠，即不同信道　上的信号互不干扰。　３）通信信道是理想的，即不考虑噪声干扰、链　路误码的影响。　４）节点在网络中均匀部署，且在数据包传输过　程中不发生移动。　４单用户分析模型　４．１单路径容量分析模型　定理１　多信道无线多跳网络中，单路径情况　下的路径容量为　５）数据包仅在源节点产生，路径上的中间节点　不产生数据包，只转发数据包。　证明单路径情况下，采用多信道技术的无　６）数据包数量远大于传输路径的长度（跳数）。　线多跳网络理想的数据包流水作业调度方案如　７）网络可利用信道数量充足。　图１所示。　模型中所用符号及说明参见表１。　表１　模型符号　；　：　：　；　：　符号　定义　符号　定义　Ｅ［Ｐ】　载荷平均长度　丁　时钟节拍　：１Ｔ　：：：　：：。：’：｝：二　…．．　……÷…一一＋…一一　路径长度（跳数）　ｐ，Ｎｓｐ　长、短路径长度　３Ｔ　Ｉ…２一＝ｊＩ……ｆ．：：：：：．　二　…一一ｆ…一一一　一…一１　４Ｔ　ｉｒ…一Ｉ一－　一　２＂一一｝…一一．－“　单路径容量　５　７１　：：二三二｛Ｉ一…一一　！Ｉ　｛：：：．：：：÷：　Ｉ！一一一　！　一一十……卜一…　｛……　　Ｉ！　．：：：：．　二　！ｉ　…一一　：　　Ｔｈｒ。　单路径吞吐量　．弛　蠡等　曩　为　６　一…一Ｉ　－５－－－［一…一ｉ－－－￣－％！…一一—Ｉ［：　口Ｉ　螽学篡　为奇　喜曩　为　７　．Ｌ＿生　广Ｉ　广ｌ　—’｛　：　８Ｔ　ｉ　Ｈ　Ｈ　Ｈ　３．２模型的基本思想　９丁１１　ｏｏｒ　ｒ　目ｆ…一一１Ｉ二……困　５　Ｉ…一一１一’－…’－－￣－－’－ＴＴ－　…一－Ｓ－－－Ｆ一…一　因为可利用信道数量充足，网络可以为每个节　…一［　…一ｆ＝　…一崮一—｝二三二二ｊ　　点分配一个缺省信道。要建立通信时，发送节点切　换到接收节点的缺省信道上与其建立通信。通信双　方节点所采用的信道与其余节点工作的信道互不　在时间１　７１，源节点ｓ切换到节点１的缺省信道　重叠，因而，该节点对的通信不会与其余节点的通　ＣＨ１上向节点１发送数据包　。在时间２Ｔ，节点　信相互干扰，从而提升网络的性能。　ｌ流水作业切换到节点２的缺省信道ＣＨ２上向节点　首先建立单用户情况下的多信道网络的路径　２转发数据包Ｐｋｔｌ。由于节点仅配备单个半双工收　容量模型。以端到端的多跳传输路径为研究对象，　发器，节点１不能同时处于发送和接收状态，源节　将数据包由源节点到宿节点的传输时间分割成一　点Ｓ也就不能在时间２Ｔ向节点１发送数据包。在　个个时钟节拍　。，　为节点问成功发送一个数据　时间３Ｔ，节点２流水作业切换到节点３的缺省信道　包所用的平均时间，然后根据网络拓扑和数据流设　ＣＨ３上向节点３转发数据包Ｐｋｔ，。同时，源节点Ｓ　计理想的数据包流水作业调度方案，分析数据包到　可以在节点１的缺省信道ＣＨ１上继续向节点１发送　达的平均周期，从而获得多信道无线传感器网络路　数据包Ｐｋｔ２。由于工作在不同的信道上，两对通信　径容量。　可以同时进行。依此方法，源节点每隔一个时钟节　然后建立多用户情况下的多信道网络容量模　拍　发送一个数据包，甫问节点流水作业从上游节　型。以多个用户路径构成的整个网络为研究对象，　点接收到数据包后，在下一时钟节拍　向下游节点　基于多信道无线网络资源竞争的本质，利用数学　转发该数据包。　模型构建基于节点竞争域的资源竞争约束关系，　假设源节点Ｓ每隔一个时钟节拍　发送一个数　然后在Ｋｅｌｌｙ资源分配基本框架的基础上，建立　据包，共向宿节点Ｄ发送ｎ个数据包。理想信道中　多信道网络容量模型。进一步地，利用网络容　数据包没有因噪声干扰、链路误码的影响而丢弃，　量模型来研究如何合理配置网络资源以优化网　按照理想的数据包流水作业调度方案，宿节点Ｄ可　络性能。　以每隔一个时钟节拍丁接收到一个数据包，从而接　第ｌ１期　王明飞等：多信道无线传感器网络容量分析模型研究　・５３・　收到所有的ｎ个数据包。那么，路径最大吞吐量为　，　又ｎ＞＞ＩＶ。，故多路径容量为　…　＝　玎　。　。　ｎｘＥ［Ｐ】　Ｎ　Ｘ　＋（ｎ一１）ｘ２ｘ　。　同理，可以证明两条路径长度之差为２、４、６…　偶数的情况，结论同上。　。证毕。　将两条路径的传输抽象为一个管道，源节点Ｓ　和寄存器节点Ｄ都是在每个时钟节拍丁向管道注入　数据包，源节点Ｓ和宿节点Ｄ均分别达到了最大发　送能力和最大接收能力，因此，再增加两点间路径　的数目不会增加两点间的最大吞吐量。证毕。　值得指出，源节点Ｓ发送的数据包经两条长度　又　＞＞　，故路径容量为　４．２多路径容量分析模型　＝　…ｊ　Ｓｕｃ　采用多路径传输技术可以解除路径上中间节　点的半双工工作方式的制约，进一步增加多信道网　络的空间复用度，提高端到端的数据吞吐量。　４．２．１路径长度之差为偶数的分析模型　定理２多信道无线多跳网络中，在源节点和　宿节点间给定两条节点不相交路径，当两条路径长　不一致的路径到达宿节点Ｄ时会出现数据包乱序，　数据包乱序并不会影响端到端的数据吞吐量。　从定理２可以看出，当两条路径长度之差为偶　数时，在源节点和宿节点间端到端的数据吞吐量可　以达到单跳传输时点对点的数据吞吐量，达到理想　状态。然而，当两条路径长度之差为奇数时，流水　作业不再如此完美。　度之差为偶数时，端到端的数据最大吞吐量为　：　』ｓｕｃ　并且，再增加两点问路径的数目不会增加两点间的　最大吞吐量。　４．２．２　路径长度之差为奇数的分析模型　假设两条路径长度之差为奇数，两条路径上的　中间节点分别流水作业转发数据包，那么，两条路　径上的数据包会在同一个时钟节拍到达宿节点。为　避免碰撞，其中一条路径上的数据包必须延缓发　送，增加了数据包的传输时延，相应地减少了端到　证明　首先，证明两条路径长度相等的情况。　不失一般性，以两条路径均为５跳的网络为例，理　想的流水作业调度方案如图２所示。　端的吞吐量。本文采用长路径上节点缓存数据包的　策略来分析端到端的吞吐量。当两条路径上的数据　包同时到达最后一个中间节点时，长路径上数据包　主动缓存，避让短路径上数据包，延缓一个时钟节　拍后再向宿节点发送。　定理３多信道无线多跳网络中，在源节点和　宿节点间给定两条节点不相交路径，当两条路径长　度之差为奇数时，端到端的数据吞吐量可以达到　Ｔｈａ：：—２Ｎｉｐ１　里　＝——＝　：　－—Ｘ‘…　２Ｎｉｐ　证明假设源节点首先向短路径发送，采用长　路径上节点缓存数据包的策略，理想的流水作业调　度方案如图３所示。　图２路径长度相等的多路径网络理想数据包调度方案　假设两条路径长度之差为ｍ。源节点由短路径　开始交替向两条路径发送数据包。两跳路径上的中　间节点分别流水作业转发数据包。经Ⅳｌ。个时钟节　类似于定理１的分析方法，可以得到路径的吞　吐量为　Ｔ　ｒ岬。　ｎｘ　Ｅ［Ｐ］　拍后，长路径上的首个数据包到达最后一个中间节　点，此时，短路径上的第（ｍ＋３）／２个数据包也将到　达最后一个中间节点。让长路径上数据包主动缓　通信学报　第２９卷　玎　玎　玎　盯　盯　盯　存，延缓一个时钟节拍后再向宿节点发送，以避让　同理，可以分析源节点首先向长路径发送数据　包的情况。经Ⅳｌ。个时钟节拍后，长路径上的首个　数据包到达最后一个中间节点时，短路径上的第　（ｍ＋１）／２个数据包也将到达最后一个中间节点。为　短路径上数据包。长路径上的最后一个中问节点在　Ⅳｌ。＋１个时钟节拍缓存数据包，在Ⅳｌ。＋２个时钟节　拍向宿节点发送数据包。进而，上游节点将延缓一　个时钟节拍向该节点发送数据包。依此类推，在　Ｍ。＋１个时钟节拍到２Ｎ：ｔｐ－１个时钟节拍，长路径上　的中间节点将依次缓存数据包一个时钟节拍。然　避免碰撞，采取长路径上节点缓存数据包的策略。　进一步地分析，该情况与源节点首先向短路径发送　数据包的情况一致，结论同上。　证毕。　可以利用图论深入分析路径长度差为奇数时　后，源节点空闲一个时钟节拍，以保证路径上的数　据包依次到达宿节点。这样，经过２Ｊ７Ｖｌ。个时钟节拍，　即２７ｖｌ。　时间后，多信道网络上的数据包调度过程　完成一个周期。　Ｋ　卜（　ｌ　１　Ｉ　Ｉ　，　●　２　・ｌ　３、　１Ｉ．．　１　．一　———＋　　ＩＩ　；　４　，　Ｉ１　　３　Ｉ，２　　’　１　，　．　！　５　Ｉ　４　３　ｒ　［　］２　６　７　Ｉ：６　５　　Ｅ　ｊ　４［　丑　３　１　，．　４　，　，　；８　ｅ　５　Ｉ！　　，　６　＿　３　　ｌｒ＿　８　ｉｊ　５　ｆ　，　６　ｌ　９　Ｉ　７　；　－　８　５　１　ｌ　１０　：９　７　８　；　－　，　１１　：１Ｏ　９　７　１２　：１１　：１０　　｝，．　！　，　ｌ　，　９　Ｉ　；　ｌ１２　：１１　，　　ｉ１０　，　●　ｉ　１４　；１３　！　，ｌ２　　乜　口Ｉ１　　Ｉ１５　ｉｌ４　１３口　１Ｏ　图３路径长度差为奇数的多路径网络理想数据包调度方案　将两条路径的传输抽象为一个管道。在这２Ｎｉｐ　个时钟节拍内，源节点有２Ⅳ１。一１个时钟节拍向管道　注入２Ｎｉｐ－１个数据包，并有１个时钟节拍空闲以避　免数据包的冲突。按照流水作业调度方案，宿节点　也将在路径延迟后，在２Ⅳｌ。个时钟节拍内从管道中　获取２＾，ｌＤ一１个数据包。那么，端到端的数据吞吐量　可以达到　２Ｎｉｐ－１ｒ　ｍａｘ　：——×　×婴　ｍ网络性能下降与数据流所经路径构成非偶图　（ｎｏｎ．ｂｉｐａｒｔｉｔｅ　ｇｒａｐｈ）有关。在非偶图中，不能将　任意一条边的两个顶点划分为两个不相交的集合。　这样，路径上的节点不能交替处于收发两种状态，　因而不能完美实现流水作业，造成网络性能下降。　５多用户分析模型　多信道无线传感器网络与单信道环境下的无　线网络不同，由于多信道技术的信道隔离性质，制　约无线网络性能的因素不再是单信道条件下的无　线链路干扰问题，而是节点所配备的单收发器的半　双工工作方式。多信道无线网络资源竞争的本质是　流经同一节点的输入输出数据流竞争该节点的单　个无线收发器资源。本节构建基于节点竞争域的资　源竞争约束模型，进而利用数学规划建立多用户多　信道无线传感器网络的容量分析模型。　５．１多信道无线网络抽象模型　多信道无线传感器网络可抽象为一个无向图　Ｇ＝（Ⅳ，Ｌ），其中，』ｖ为网络中节点的集合，Ｌ为网络　中通信链路的集合。网络的链路ｆ定义为ｌｉｉ＝（Ｎｉ，Ｍ）　∈Ｌ，即ｆ所关联的两个节点间存在一条通信链路。　定义１　Ｄ　Ｌ且Ｄ满足　１）ＶＩｊ￣＝（Ｎｊ，　）∈Ｄ，（Ｍ＝Ｍ）ｕ（Ｍ＝Ｍ）　２）　＝（Ⅳｓ，Ｎｔ）￣Ｄ，（Ｍ≠Ⅳｓ）ｎ（Ｍ≠Ｍ）　则称Ｄ为网络Ｇ中节点Ｍ的节点竞争域（ｎｏｄｅ　ｃｏｎｔｅｎｔｉｏｎ　ｄｏｍａｉｎ）。　可以看出，节点竞争域Ｄ是网络Ｇ　中与节点　相关联的通信链路的集合。设Ｄ：Ｄ∈Ｄ　２Ｌ表示　网络中所有节点竞争域的集合。　设网络中一对通信的源宿节点对＜Ｎｓ，Ｎｄ＞表示　一个用户的数据流，数据流的方向总是由源节点　流向宿节点Ⅳｄ。设Ｆ为网络中所有用户数据流的集　合，定义向量　＝　．厂∈　，即为用户数据流．厂的端　到端吞吐量所占链路实际容量的比例因子。定义路　径为由源节点到宿节点的通信链路的顺序序列。设　第１１期　王明飞等：多信道无线传感器网络容量分析模型研究　・５５・　尺为网络中所有用户数据流的路径的集合。定义０—１　矩阵Ａ＝（ａｆｒ，．厂∈　ｒＥＲ）描述用户数据流与路径之　问的关系，如果数据流．厂使用路径ｒ进行传输，则　ａｆｒ＝ｌ；否则，ａｐ＝Ｏ。定义向量ｒ＇＝ｆｙ，，ｒＥＲ），Ｙ，为路　果数据链路在节点竞争域内，即ｆ∈Ｄ，则ｂＤｌ＝１；　否则，ｂｏｌ＝０。定义向量仃＝（ｏｚ，ｆ∈Ｄ）为所有数据链　路的带宽比例因子。那么，节点竞争域内的链路吞　吐量约束的矩阵表示形式为　Ｂａ≤１　（２）　径，．所传输数据的吞吐量所占链路实际容量的比例　因子。一个用户的数据流的端到端吞吐量为并行传　输的所有路径的端到端吞吐量之和。因此，用户数　５．２．２流经同一链路的路径竞争约束分析模型　当网络中的某一链路传输来自不同路径的数　据流厂的吞吐量所占链路容量的比例因子可表示为　ｘ／＝∑（ａｐＸｙ，）　ｒＥＲ　用矩阵表示为　Ｘ＝ＡＹ　（１）　５．２多信道网络资源约束分析模型　基于节点竞争域的网络资源约束分析过程分　为三个步骤：首先分析同一个节点竞争域中链路之　间的竞争约束；然后分析多个用户数据流在同一传　输链路上的竞争约束；最后，将两类约束合二为一，　建立基于节点竞争域的资源约束模型。　５．２．１节点竞争域内链路竞争约束分析模型　设节点的实际容量即节点的实际收发速率为　Ｃ　，ｎ∈ＪⅣ。假设在无干扰情况下的无线网络数据链　路的实际容量为Ｃｆ，ＺＥＬ。易知，链路的实际容量　等于节点的实际容量，即Ｃｆ＝Ｃ　。　多信道无线网络中，流经同一节点的输入输出　数据链路竞争该节点的单个收发器资源。因而，节　点竞争域内的所有链路的实际吞吐量之和受限制　于节点的实际容量。因此，节点竞争域内的链路吞　吐量约束可表示为　Ｔｈｒ（１）＜￣ｃ　，　Ｔｈｒ（１）＜￣ｃｆ　：　将约束条件进行归一化描述。设ｏ　为数据链路　的带宽比例因子，即流经链路ｆ的实际吞吐量占链　路实际容量的比例。那么，节点竞争域内的链路吞　吐量约束又可表示为　∑６，Ｃｌ￣Ｃ１，即∑Ｇｆ≤１　ｋＤ　ｆ∈Ｄ　由节点竞争域的定义可知，节点数目为ｎ的多　信道网络，可以划分为ｎ个节点竞争域。然而，如　果网络中某节点的度为１，即与该节点关联的链路　仅有１条，不存在竞争问题，则将其从节点竞争域　集合中去掉。假设网络可划分为ｋ个节点竞争域，　即Ｄ＝｛Ｄ１，Ｄ２，…，Ｄ　ｌ。定义０—１矩阵Ｂ＝（ｂＤｌ，Ｄ∈　】Ｅ），ｚ∈Ｌ）描述节点竞争域与数据链路之间的关系，如　据包时，不同路径的数据包在同一链路上形成竞　争。设ｙ，ｆ，ｚ∈Ｌ，ｒＥＲ为路径ｒ所占链路ｚ实际容量　的比例因子，若链路Ｚ上传输ｍ条路径的数据流，　则在ｆ上的路径吞吐量约束可归一化表示为　∑Ｙ：≤ｏ　ｉ＝１　路径ｒ的端到端吞吐量应等于路径上的所有链　路中瓶颈链路的吞吐量，即路径端到端吞吐量所占链　路实际容量的比例因子ｙｒ＝　｛　｝。因此，，，ｚ条路　径的数据流在链路Ｚ上的竞争路径约束为　∑Ｙ，≤ｏｚ　ｉ＝１　定义０．１矩阵Ｇ＝（　ｌＥＬ，ｒＥＲ）描述数据链路　与路径之间的关系，如果数据链路在路径，．的链路　序列中，则ｇｌｒ＝１；否则，肌＝Ｏ。因此，流经同一　链路的路径的吞吐量约束的矩阵形式为　ＧＹ≤ｏ　（３）　５．２．３竞争约束分析模型的整合　可将式（２）、式（３）整合为如下不等式约束　曰Ｇｙ≤１　令矩阵Ｈ＝ＢＧ，则多信道无线多跳网络的竞争　约束条件可用矩阵表示为　日ｙ≤１　（４）　矩阵日在多信道无线多跳网络中有其实际的　意义。日＝（．１ｚＤ，’ＤＥＤ，ｒＥＲ）表示路径，．的链路序列　中在节点竞争域Ｄ中的链路数目。　综合式（１）、式（４），多信道无线多跳网络的资源　竞争约束可用矩阵标准型表示为　ｆ　—ＡＹ＝０　ｆ　１日Ｙ一１≤０　其中，　和ｙ为变量矩阵；Ａ和日为参数矩阵。　５．３　多用户网络容量分析模型的建立　按照Ｋｅｌｌｙ资源分配基本框架，以比例公平模　・５６・　通信学报　第２９卷　型［１７１为基础，选取效用函数Ｕｊ（ｘｆ）＝ｌｏｇ（ｘｓ）。多信道　无线多跳网络容量分析模型可以描述为如下优化　问题的求解。　最大化　∑ｌｏｇ（ｘｆ）　ｆｃＦ　约束条件　—Ａｙ＝０　Ｈｙ一１≤Ｏ　＞０　Ｙ　０　其中，ｙ为多信道网络中路径带宽比例因子向量，　为用户数据流的带宽比例因子向量，矩阵Ａ表示　用户使用多路径传输的情况，矩阵日表示路径与节　点竞争域的关系。可以证明该优化问题在可行域内　存在惟一的最优解。设模型的最优解为Ｘ　＝　１　，　２　，…，Ｘｎ　】，则用户数据流，的实际带宽为Ｗｆ＝ｘｎ　×Ｃｆ。Ｃｚ可通过公式Ｅ［Ｐ］／Ｔｓ　。求得。　５．４模型的集中式求解与应用　用户给定网络拓扑Ｇ和链路带宽Ｃ　一　１　０　，以及用户　数据流Ｆ的路由信息　。求解网络容量分析模型可　ｙ　Ａ≤　０　一　以完成以下功能。　１）为用户提供该网络的无线资源的约束关系；　２）判断用户的带宽需求向量Ｘ＝　１，Ｘ２，…，Ｘｎ］　在当前网络条件下是否可行；　３）获得该网络的最优资源分配向量Ｘ　＝　１　，　￥　…，，　Ｊ　ｏ　５．４．１求解网络带宽约束　确定给定网络的约束条件，需要确定参数矩阵　Ａ和日。矩阵Ａ可通过用户输入的数据流　和数据　流使用的路由信息　确定。矩阵日由日＝　Ｇ求得。　由给定网络的节点竞争域Ｄ确定，Ｇ可由Ｆ和　确定。节点竞争域是与节点相关联的所有链路的集　合。给定网络拓扑图Ｇ，就可以方便地得到网络的　节点竞争域。　５．４．２求解网络带宽需求可行性　确定给定网络的约束条件后，判断用户的带宽　需求向量Ｘ　＝　，Ｘ２　，…，Ｘｎ　］在当前网络条件下是　否可行，可转化为求解下面的优化问题：　最大化Ｐ　约束条件　其中，Ｐ表示在当前网络约束和用户带宽需求条件　下，路径带宽比例因子ｙ的可扩展系数。设该优化　问题的最优解为Ｐ　，若ｐ　≥１，则Ｘ　向量可行；若　ｐ　＜１，则Ｘ’向量不可行。　５．４．３求解网络最优带宽分配　采用Ｌａｇｒａｎｇｅ乘子法求解优化问题的最优解。　该优化问题的Ｌａｇｒａｎｇｅ函数为　Ｌ（Ｚ，Ｙ，　，／ｚ）＝∑ｌｏｇ（ｘＩ）－２　（ｘ—Ａｙ）　（１－ＨＹ）　，∈Ｆ　ｋ　＝∑（１ｏｇ（ｘ／）一２ｉｘ１）＋（２　Ａ　）ｙ＋∑　ｆＥＦ　ｉ＝１　ｋ　ｋ　＝∑（１ｏｇ（ｘ／）一　，）＋∑　㈩一∑　，）），＋∑　设Ｘ　＝　ｌ　，Ｘ２　，…，Ｘｎ　】　。为该优化问题的最优　解，根据Ｋｕｈｎ．Ｔｕｃｋｅｒ条件，存在Ｙ　＝［ｙ１　，Ｙ２　，…，　ｙｎ　］Ｔ，　＝　ｌ　，五２　，…，　］Ｔ，，ｆ　＝　ｌ　２　，…，　］Ｔ满　足如下等式和不等式：　Ｌ　，ｙ　，　，　）＝０；　，ｙ　，　，　）＝０；　＝ＡＹ　；ＨＹ　一１≤０；　≥０；／ｔ／＊Ｔ（ＨＹ　一１）：０。　求解上述等式和不等式组，即可得到上述优化　问题的最优解。　５．５模型的分布式求解与应用　虽然上面的优化问题可以直接求解，但需要　知道全部流的信息，这在实际网络中是不可能实　现的。所以需要将求解算法转化成网络可执行的　分布式算法。本小节给出网络容量分析模型的分　布式求解方法及其在流量控制和路由优化中的　应用。　５．５．１多信道网络的流量控制　鉴于多路径传输数据流不会与其他数据流的　路径相交，从而可以独立计算，本节假设数据流采　用单路径传输。因此，５－３节中的容量分析模型可　简化为如下最优化问题的求解　最大化　∑ｌｏｇ（ｘＩ）　ｒ∈Ｆ　约束条件ＨＸ一１≤０　Ｘ≥０　利用优化理论中的原始一对偶方法进行分析，　第ｌ１期　王明飞等：多信道无线传感器网络容量分析模型研究　则其对应的Ｌａｇｒａｎｇｅ函数为　Ｌ（Ｘ，　）＝∑ｌｏｇ（ｘ：）一　（ＨＸ－１融　）　｜ＥＦ　＝∑（１ｏｇ（ｘ：）－ｘ／∑　）＋∑五　ｆＥＦ　ｉ＝１　ｉ＝１　图５　ＭａｘＮｅｔ模型　其中，　＝　１，２２，…，　为Ｌａｇｒａｎｇｅ乘子，ｈ／ｓＹ￣　前面分析已知，多信道网络中流的最大传输速　流－厂在节点竞争域ｉ中的链路数。Ｌａｇｒａｎｇｅ函数对　应的关于变量　的对偶函数为　Ｄ（２）＝ｍａｘ　Ｌ（Ｘ，　）　Ｋ　Ｋ　∑ｌｏｇ（）－＂　）＋∑　当　：　，∈Ｆ　ｉ＝１　ｉ＝１　∑　ｉ＝１　当ｘｆ＝０　则原始问题对应的对偶问题为：ｍｉｎ（Ｄ（２））。　设对偶问题的最优解为　，则原始问题的最　１　置　优解为ｘｆ　＝　÷一。其中，∑　表示数据流从　扭　ｉ＝１　源节点到宿节点所经历的所有节点竞争域的价格　之和。２ｉ＊ｈ　表示节点竞争域内的所有链路的价格　之和。将这种使用总的价格作为反馈信号的网络　模型称为多信道网络的总价（ＳｕｍＮｅｔ）模型，如　图４所示。总价模型可以反映网络一个整体的信　息，可以证明通过这种模型得到的算法达到比例　公平。　图４　ＳｕｍＮｅｔ模型　在互联网的拥塞控制体系结构研究中，　Ｗｙｄｒｏｗｓｋｉ　Ｂ等【２　］提出了一种最大价格（ＭａｘＮｅｔ）　模型，如图５所示。这种模型不是反馈给源端所　历经的链路的总价格，而是选择链路中的价格最　大的那个值。文献［２２１分析通过选择适当的效用　函数，使用ＭａｘＮｅｔ模型的算法对于一般的源端　有不同需求函数的网络可以达到全局的最大最小　公平，而且不需要全局信息也无需链路保存每个　流的状态。　率受流所经历的所有节点中瓶颈节点竞争域的限　制，只需要使流经瓶颈节点竞争域的流的总速率不　要超过实际容量就可以控制拥塞。因此，本文主要　考虑网络中的瓶颈节点的竞争域，采用所有节点竞　争域中最大的价格作为反馈信号的网络模型，称为　多信道网络的最大价格模型。则数据流．厂对应的最　优解为　１　Ｘｆ　该表达式具有实际意义：　为数据流．厂在节点　竞争域中的链路数；　为节点竞争域中数据流的个　数；）ｃｉ＊ｈ矿表示节点竞争域内的所有链路数。　为便于表述，并区别于网络拓扑图中链路数的　概念，本文引入“虚拟链路数”的概念。　定义２虚拟链路数　表示流经节点ｉ的所有　流在该节点竞争域内的链路数之和。　＝∑（　）　ｆＥＦｉ　其中，　表示流，在提供Ｑｏｓ带宽保证的网络中的　ＱｏＳ权值。　表示流，流经节点ｆ的竞争域的链路数。　那么，在ＭａｘＮｅｔ模型中，　：　ｍａｘ（Ｖ，，ｉ＝１，２，…，　）。　下面建立多信道网络的流量控制算法。因为节　点在某一时刻只能在竞争域内的某一个链路上工　作，需要设定时间窗口统计一段时间内节点的工作　状态，包括流经节点的流的数目和相应流在节点竞　争域的虚拟链路数。流的标识信息捎带在传输的报　文中。实现过程如图６所示，多信道无线传感器网　络的流量控制算法如图７所示。　ｑｌ　１　ｍａｘ（ｐ１，ｑ１）　ｍｏｘ（ｐ，￣ｌ，　）　图６　ＭａｘＮｅｔ模型的实现　通信学报　第２９卷　（１）网络端　在时间窗口ｆ＝１，２，…，网络端节点Ｒ执行以下步骤。　１）统计所有经过节点Ｒ竞争域的流的数目　。）以及相应流的链路数ｈ（０；　２）计算节点Ｒ的新的虚拟链路数：　（ｆ＋１）＝Ａ（ｆ）Ａ（　：　３）对于所有经过节点Ｒ的数据流，解析数据包，得到数据流携带的　虚拟链路数　，将　与新算出的节点Ｒ的新的虚拟链路数ＶＲ（ｔ＋Ｉ）ＬＬ　较，如果ＶＲ（ｔ＋Ｉ）＞Ｖｆ，则更新数据包中的　，　（Ｈ１）；　４）若Ｒ为宿节点，则将虚拟链路数　反馈给流的源节点。　（２）源端　在时间窗口Ｆ１，２，…，源节点ｓ执行以下步骤：　１）解析数据包，得到反馈的虚拟链路数　；　２）计算源节点ｓ新的发送速率　ｆ＋１）＝ｃｔ／　３）在下一时刻以ｘｆ（ｔ＋１）的速率发送数据包，并将ｖｆ的值填充在数据包中　图７多信道无线传感器网络的流量控制算法　５．５．２　多信道网络的路由优化　在进行路由选择时应尽量避免将瓶颈节点加　入路由，一方面可以避免数据流的最大传输速率受　到瓶颈限制，另一方面可以避免影响瓶颈节点已有　的通信，加重拥塞。本文将模型中提出的虚拟链路　数的概念应用到路由优化工作中，将其作为路由选　择时的重要参考依据，从而优化网络的整体性能。　网络中每个节点根据网络运行情况实时维护　虚拟链路数。用户在建立路由时，根据节点的虚拟　链路数可以实时求解选择该节点为路由节点后的　最大传输速率，从而根据能否满足带宽需求来决定　是否将该节点加入路由。一般网络中，在满足连通　性等指标的基础上，可以尽量选择虚拟链路数小的　节点加入路由。如果应用到提供ＱｏＳ保证的网络，　可以判断该节点加入路由后能否满足带宽需求。　６模型验证与性能分析　本文利用网络仿真软件ＮＳ．２－３　１　ｆ２ｏ］来验证模型　的正确性。物理层采用ＤＳＳＳ机制，ＭＡＣ层为在　８０２．１ｌ和ＲＤＴＥ２１］协议基础上添加实现的多信道　ＭＡＣ协议，网络层采用静态配置路由，传输层采　用ＵＤＰ协议，应用层为ＣＢＲ数据流。无线传感器　网络中的竞争窗口参数ＣＷ通常设为固定值【１剞，本　文实验取值为３１。由于信道切换时延为某一固定　值，并仅跟物理层芯片有关，本文未考虑信道切换　时延。通过调整数据包的发送时间间隔来控制流量　负载。实验结果为ｌ０次实验的平均值。具体实验　参数值见表２。　表２　仿真实验参数　参数名称　数值　参数名称　数值　Ｄａｔａ　ｐａｙｌｏａｄ　５００ｂｙｔｅ　ＤＩＦＳ　５Ｏｕｓ　ＩＰ　ｈｅａｄｅｒ　１６０ｂｉｔ　ＳＩＦＳ　１０ｇｓ　ＭＡＣ　ｈｅａｄｅｒ　２４Ｏｂｉｔ　Ｓｌｏｔ　Ｔｉｍｅ　２０ｇｓ　ＰＨＹ　ｈｅａｄｅｒ　１９２ｂｉｔ　ｌｇｓ　ＲＴＳ　３６８ｂｉｔ　ＣＷ　３１　ＣＴＳ　３２Ｏｂｉｔ　ＣＳＤｅｌａｙ　０　ＡＣＫ　３２０ｂｉｔ　Ｄａｔａ　Ｒａｔｅ　１Ｍｂｉｔ／ｓ　ＤＴＣ　３６８ｂｉｔ　Ｂａｓｉｃ　Ｒａｔｅ　ｌＭｂｉｆｓ　流水作业的时钟节拍　。可以由下式给出：　Ｔ呲＝Ｔｃｓ＋ＤＩＦｓ＋’ｒ　ｓ＋６＋ＳＩＦｓ＋Ｔｃ　ｓ＋６＋ＳＩＦｓ＋　ＴＤ　＋６＋ＳＩＦＳ＋Ｔ　６＋ＳｌＦＳ＋ＴＤｆｒｃ＋６＋ｗ　其中，　ｓ为信道切换时延；ＤＩＦＳ和ＳＩＦＳ均为帧间　间隔；ＴＲＴＳ、ＴｃＴｓ、ＴＡｃＫ、ＴＤＴｃ分别是传输ＲＴＳ、　ＣＴＳ、ＡＣＫ、ＤＴＣＬ２　报文所用的时间；　ＡＴＡ为传　输一个完整的数据帧所用的时间，该数据帧包括物　理层头部、链路层头部、网络层头部和有效载荷；　为发送数据包所用的平均等待时间（包括发送　前的等待和冲突产生的退避）；　为无线信号传播　时延。　根据模型和仿真实验参数，可以计算时钟节拍　Ｔｓｕｃ＝６　３７３ｇｓ，链路实际容量Ｃｌ＝０．６２７　７Ｍｂｉｔ／ｓ。　单用户网络仿真实验分别采用类似图１～图３的　网络拓扑，在路径长度一定的条件下，调节源节点　的发包间隔，使到达宿节点的吞吐量达到最大值。　模型计算结果与仿真实验结果分别如图８　图１Ｏ所　示。其中，多路径网络实验结果中的两条路径的长　度用“一”隔开表示。定义误差ｅ＝ｌＶ理论一Ｖ实　ｏｌ／Ｖ螂，　误差曲线分别如图１１～１３所示。可以看出，路径容　量分析模型计算得到的理论容量值在不同的路径　数和路径长度时，都比较准确地反映了实际容量的　变化趋势和上边界。单路径网络容量模型的误差在　３％以内，多路径网络容量模型的误差在９％以内。　多路径网络容量模型的误差大于单路径网络　容量模型的误差。单路径网络的瓶颈节点在路径上　的中间节点，可以利用源节点增加数据包发送速率　使路径上传输的数据包尽可能实现流水作业，源节　点发送速率过大造成的丢包并不会影响整条路径　的传输时间。而多路径网络的瓶颈节点就是源节　点，源节点增加发送速率造成的丢包会浪费路径的　第１１期　王明飞等：多信道无线传感器网络容量分析模型研究　传输时间，造成性能下降。　误差随路径长度增加而增加。这是因为路径越　长，数据包能在整条路径上完整实现流水作业传输　的概率越小。　多用户网络仿真实验采用图１４所示的网络拓　扑仿真。图中有两个用户数据流，流　的源节点为　Ｓ１，宿节点为Ｄ１，所采用的路径为／＇１＝［（Ｓ１，１），（１，２），　（２，Ｄ１）］；流，２的源节点为Ｓ２，宿节点为Ｄ２，所采　用的路径为ｒ２＝［（Ｓ２，１），（１，２），（２，３），（３，４），（４，Ｄ２）］。利　用模型可以计算得到两条流的最优发送速率均为　ｃｄ４，网络中两流之和为ｃｆ／２。仿真实验流．＾、流　、两流之和的最大吞吐量分别为０．３０８４Ｍｂｉｔ／ｓ、　０．１５４２３Ｍｂｉｔ／ｓ、０．１５４２１Ｍｂｉｔ／ｓ，误差均约为１．７６％。　可见，多用户网络容量模型也具有较高的准确度。　仿真实验分析多信道网络中数据流负载对网　络吞吐量的影响关系。单路径网络、多路径网络　以及多用户网络的仿真实验结果分别如图１７一图　１９所示。可见，网络的吞吐量开始随着数据流负　载的增加而增加，当达到最大值后，单路径网络　的吞吐量保持不变，但可以验证重负载时数据包　时延性能会明显下降。多路径网络的吞吐量达到　最大值后随负载的增加而减小。这也说明了流量　控制的必要性。　仿真实验测试多信道网络流量控制算法的性　能。针对多用户网络分别采用流量控制算法和不　采用流量控制算法进行仿真实验，获得数据包的　传输时延。限于篇幅，仅给出流１的仿真实验结　果分别如图１５、１６所示，流２的仿真实验结果与　流１基本相同。可见，采用流量控制算法的数据　包传输时延性能明显优于不采用流量控制算法的　数据包传输时延性能。利用网络容量分析模型可　以得到用户最佳的发送速率，从而保证网络整体　的性能。　图８单路径网络容量模型与实验结果对比　路径长度　图９长度差为偶数的多路径网络模型与实验结果对比　路径长度　图１Ｏ长度差为奇数的多路径网络模型与实验结果对比　路径长度　图ｌ１单路径网络模型的误差曲线　路径长度　图１２长度差为偶数的多路径网络模型误差曲线　通信学报　第２９卷　路径长度　图１３长度差为奇数的多路径网络模型误差曲线　图ｌ４多用户网络仿真实验拓扑　数据包序列号　图１５采用流控算法的包传输时延分布　数据包序列号　图１６未采用流控算法的包传输时延分布　图１７单路径网络吞吐量与负载的关系　发包间隔／ｍｓ　图１８多路径网络吞吐量与负载的关系　发包间隔／ｍｓ　图１９多用户网络吞吐量与负载的关系　７结束语　本文构建的容量分析模型可以准确地描述多　信道无线传感器网络容量的上边界，模型计算简　单，对网络部署和协议设计具有一定的指导意义。　本文的假设对模型的实际应用影响较小。假　设１）、２）、３）、６）是在实际网络应用中较容易满足　的；假设４）中节点的移动只要不离开通信对方节　点的传输范围，就不影响网络的性能；假设５）中　路径上的中间节点也产生数据包的情况可以按照　多用户网络容量模型进行分析。假设７）中网络信　第１１期　王明飞等：多信道无线传感器网络容量分析模型研究　・６１・　道数量充足只需要满足在两跳干扰范围内的活跃　［１６】刘永强．无线Ｍｅｓｈ网络带宽分析及优化技术研究［Ｄ】．北京大学．　节点使用的信道不重复即可，两跳干扰范围外的　２００６．　节点可以复用信道。　ＬＩＵ　Ｙ　Ｑ．Ｒｅｓｅａｒｃｈ　ｏｎ　Ｂａｎｄｗｉｄｔｈ　Ａｎａｌｙｓｉｓ　Ｍｏｄｅｌｓ　ａｎｄ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ　Ｄｅｓｉｇｎ　ｆｏｒ　Ｗｔｒｅｌｅｓｓ　Ｍｅｓｈ　Ｎｅｔｗｏｒｋ［Ｄ］．Ｐｅｋｉｎｇ　Ｕｎｉｖｅ￣ｉｔｙ．　２００６．　参考文献：　［１７］ＫＥＬＬＹＦＥ　Ｃｈａｒｇｉｎｇａｎｄ　ｒａｔｅ　ｃｏｎｔｒｏｌｆｏｒ　ｅｌａｓｔｉｃｔｒａｆｉｆｃ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ，１９９７，（８）：３３－３７．　［１］ｈｔｔｐ：／／ｗｗｗ．ｗｓｎ．ｏｒｇ．ｃｎ／［ＥＢ／ＯＬ］．２００８．　［１８】ＫＥＵ　Ｆ只ＭＡＵＬＬＯ０　Ａ，ＴＡＮ　Ｄ．Ｒａｔｅ　ｃｏｎｔｒｏｌ　ｉｎ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　［２］ＧＵＰＴＡ只ＫＵＭＡＲ　Ｅ　Ｔｈｅ　ｃａｐａｃｉｔｙ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｎｅｔｗｏｒｋｓ：ｓｈａｄｏｗ　ｐｒｉｃｅｓ，ｐｒｏｐｏｒｔｉｏｎａｌ　ｆａｉｒｎｅｓｓ　ｎａｄ　ｓｔａｂｉｌｉｔｙ　【Ｊ】＿Ｊｏｕｒｎａｌ　ｏｆ　ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　ｈＴｅｏｒｙ，２０００，４６（２）：３８８—４０４．　ｏｆ　ｈｔｅ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ　Ｓｏｃｉｅｔｙ，１９９８（４９）：２３７－２５２．　【３】ＧＲＯＳＳＧＬＡＵＳＥＲ　Ｍ，ＴＳＥ　Ｄ　Ｎ　Ｃ．Ｍｏｂｉｌｉｔｙ　ｉｎｃｒｅａｓｅｓ　ｔｈｅ　ｃａｐａｃｉｔｙ　ｏｆ　【１９】ＸＵＥ　ＬＩ　Ｂ，ＮＡＨＲＳＴＥＤＴ　Ｋ．Ｐｒｉｃｅ—ｂａｓｅｄ　ｒｅｓｏｕｒｃｅ　ａｌｌｃｏａｔｉｏｎ　ｉｎ　ａｄ　ｈｏｃ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ／ＡＣＭ　Ｔｒａｎｓ　ｏｎ　Ｎｅｔｗｏｒｋｉｎｇ，　ｗｉｒｅｌｅｓｓ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　ｌｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　２００２，１０（４）：４７７—４８６．　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｑｕａｌｉｔｙ　ｏｆ　Ｓｅｒｖｉｃｅ（ＩＷＱｏＳ）［Ｃ］．２００３．１９—９６．　［４］ＫＯＺＡＴ　Ｕ　Ｃ，ＴＡＳＳＩＵＬＡＳ　Ｌ．Ｔｈｒｏｕｇｈｐｕｔ　ｃａｐａｃｉｔｙ　ｏｆｒａｎｄｏｍ　ａｄ　ｈｏｃ　［２０］ｈｔｔｐ：／／ｗｗｗ．ｉｓｉ．ｄｅｕ／ｎｓｎａｍ／ｎｓ／［ＥＢ／ＯＬ］．２００６．　ｎｅｔｗｏｒｓｋ　ｗｉｔｈ　ｉｎｆｒａｓｔｒｕｃｔｕｒｅ　ｓｕｐｐｏｒｔ【Ａ】．ＡＣＭ　Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　【２１】Ｒ１ＴＥＳＨ　Ｍ，ＨＩＭＡＮＳＨＵ　Ｇ　ＳＡＭＩＲ　Ｒ　Ｄ．Ｍｕｌｉｔｃｈａｎｎｅｌ　ＭＡＣ　ｐｒｏｔｏ—　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ（ＭｏｂｉＣｏｍ’０３）［Ｃ】．　ｃｏｌｓ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　ＳＥＣＯＮ　２００６［Ｃ１．　Ｓａｎ　Ｄｉｅｇｏ，ＣＡ，２００３．５５—６５．　Ｒｅｓｔｏｎ，ＶＡ，２００６．３９３—０４１．　［５】ＳＵ　ＹＯＮＧ　ＳＨＩＶＫＵＭＡＲ　Ｋ．Ｏｎ　ｈｔｅ　ｃａｐａｃｉｔｙ　ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　ａｄ　［２２］ＷＹＤＲＯＷＳＫＩ　Ｂ，ＺＡＫＥＲＭＡＮ　Ｍ．ＭａｘＮｅｔ：ａ　ｃｏｎｇｅｓｔｉｏｎ　ｃｏｎｔｒｏｌ　ｈｏｃ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ　ｕｓｉｎｇ　ｄｉｒｅｃｔｉｏｎａｌ　ａｎｔｅｎｎａｓ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｒａｃｈｉ￣ｃｍｒｅ　ｆｏｒ　ｍａｘｍｉｎ　ｆａｉｒｎｅｓｓ［Ｊ］．ＩＥＥＥ　Ｃｏｍｍｕｎｃａｔｉｏｎ　ＬｅＲｅｒｓ，　ｈｔｅ　４ｔｈ　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｍｏｂｉｌｅ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｋｉｎｇ　２００２，６（１２）：５２１—５１４．　＆Ｃｏｍｐｕｔｉｎｇ（ＭｏｂｉＨｏｃ’０３）［Ｃ】．Ｍａｒｙｌａｎｄ，２００３．１０８—１１６．　【６】ＫＹＡＳＡＮＵＲ　Ｅ　ＶＡＩＤＹＡ　Ｎ．Ｃａｐａｃｉｔｙ　ｏｆ　ｍｕｌｉｔ—ｃｈａｎｎｅｌ　ｗｉｒｅｌｅｓｓ　ｎｅｔ－　作者简介：　ｗｏｒｋｓ：Ｉｍｐａｃｔ　ｏｆ　ｎｕｍｂｅｒ　ｏｆ　ｃｈａｎｎｅｌｓ　ａｎｄ　ｉｎｔｅｒｆａｃｅｓｆＡ】．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｔｅ　ＡＣＭ　Ｍｏｂｉｃｏｍ［Ｃ］．Ｃｏｌｏｇｎｅ，２００５．４３—５７．　王明飞（１９７９．），男，山东金乡人，　［７】　刘雨，望育梅，邓辉．无线传感器网络的容量研究综述［Ｊ１．计算机　北京理工大学博士生，主要研究方向为无　科学，２００６，３３（４）：３９—４１．　线传感器网络、计算机网络与通信。　ＬＩＵ　ＷＡＮＧＹＭ，ＤＥＮＧＨ．Ｔｈｅ　ｃａｐａｃｉｔｙｐｒｏｂｌｅｍ　ｏｆｗｉｒｅｌｅｓｓ　ｓｅｎ—　ｓｏｒ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅｓ，２００６，３３（４）：３９—４１．　一鋈　【８】ＢＩＡＮＣＨＩ　Ｇ　Ｐｅｒｆｏｒｍａｎｃｅ　ａｎａｌｙｓｉｓ　ｏｆ　ｔｈｅ　ＩＥＥＥ　８０２．１１　ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｏｒｄｉｎａｔｉｏｎ　ｆｕｎｃｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｊｏｕｒｎａｌ　ｏｎ　Ｓｅｌｅｃｔｄｅ　Ａｒｅａｓ　ｉｎ　Ｃｏｍｒｎｕ—　ｎｉｃ撕ｏｎｓ，２０００，１８（３）：５３５－５４７．　［９］ＺＩＯＵＶＡ　Ｅ，ＡＮＴＯＮＡＫＯＰＯＵＬＯＳ　Ｔ　ＣＳＭＡ／ＣＡ　ｐｅｒｆｏｒｍａｎｃｅ　ｕｎｄｅｒ　慈林林（１９５０一），男，安徽桐城人，　ｈｉｇｈ　ｔｒａｆｆｉｃ　ｃｏｎｄｉｉｔｏｎｓ：ｔｈｒｏｕｇｈｐｕｔ　ａｎｄ　ｄｅｌａｙ　ａｎａｌｙｓｉｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　北京理工大学教授、博士生导师，主要研　Ｃｏｍｐｕｔｅｒ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００２，２５（３）：３１３—３２１．　究方向为移动计算、人工智能等。　［１Ｏ】ＷＵ　Ｈ，ＰＥＮＧ　Ｙ　ＬＯＮＧ　Ｋ，ｅｔ　ａ１．Ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｒｅｌｉａｂｌｅ　ｔｒｎａｓｐｏｒｔ　ｐｒｏｔｏｃｏｌ　ｏｖｅｒ　ｍＥＥ　８０２．１１　ｗｉｒｅｌｅｓｓ　ＬＡＮ：ａｎａｌｙｓｉｓ　ａｎｄ　ｅｎｈａｎｃｅｍｅｎｔ［Ａ］．　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆＩＥＥＥ　ＩＮＦＯＣＯＭ【Ｃ】．Ｎｅｖａｄａ，ＵＳＡ，２００２．５９９—６０７．　【１１】ＨＯＵ　Ｔ　Ｃ，ＴＳＡＯ　Ｌ　Ｆ　Ａｎａｌｙｚｉｎｇ　ｔｈｅ　ｔｈｒｏｕｇｈｐｕｔ　ｏｆ　ＩＥＥＥ　８０２．１１　ＤＣＦ　ｓｃｈｅｍｅ　ｗｉｔｈ　ｈｉｄｄｅｎ　ｎｏｄｅｓ［Ａ］．Ｐｒｏｃ　ｏｆ　ｈｔｅ　ＩＥＥＥ　Ｖｅｈｉｃｕｌａｒ　Ｔｅｃｈｎｏｌｏｇｙ　詹平（１９６４－），男，湖北随州人，北京　Ｃｏｎｆ［Ｃ］．Ｈｏｒｉｄａ，２００３．２８７０—２８７４．　【１２］肖永康．无线ａｄ　ｈｏｃ网络中ＭＡＣ协议和ＴＣＰ的性能研究【Ｄ】．清　信息高技术研究所高级工程师，主要研究方　华大学，２００４．　向为无线通信、计算机网络与通信。　ＸＩＡＯＹＫ．ＰｅｒｆｏｒｍａｎｃｅＲｅｓｅａｒｃｈ　ｏｎｔｈｅＭＡＣＰｒｏｔｏｃｏｌａｎｄＴＣＰｉｎ　Ｗｉｒｅｌｅｓｓ　Ａｄ　Ｈｏｃ　Ｎｅｔｗｏｒｓｋ［Ｄ］．Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，２００４．　［１３】ＸＵＣＣ，ＹＡＮＧＺＫ．Ｎｏｎ－ｓａｔｕｒａｔｅｄｔｈｒｏｕｇｈｐｕｔ　ａｎａｌｙｓｉｓｏｆＩＥＥＥ　８０２．１１　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｌ￣；［Ｊ］．ＩＦＡＣＥ　１１　ＡＮＳ　ＩＮＦ＆ＳＹＳ　２００６，８９（５）：１６７６—１６７８．　［１４】柯欣，孙利民．多跳无线传感器网络吞吐量分析［Ｊ】＿通信学报，　２００７，２８（９）：７８—８４．　徐勇军（１９７９。），男，安徽安庆人，　ＫＥ　Ｘ，ＳＵＮ　Ｌ　Ｍ．Ｔｈｒｏｕｇｈｐｕｔ　ａｎａｌｙｓｉｓ　ｉｎ　ｍｕｌｉｔ—ｈｏｐ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　博士，中国科学院计算技术研究所助理研　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００７，２８（９）：７８—８４．　究员，主要研究方向为无线传感器网络、　［１５】刘永强，严伟，代亚非．一种无线网络路径容量分析模型［Ｊ］．软件　低功耗设计。　学报，２００６，１７（４）：８５４—８５９．　ＬＩＵ　Ｙ　Ｑ，ＹＡＮ　ｗ，ＤＡＩ　Ｙ　Ｆ　Ａ　ｐａｔｈ　ｃａｐａｃｉｔｙ　ａｎａｌｙｔｉｃａｌ　ｍｏｄｅｌ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２００６，１７（４）：８５４－８５９．