无线传感器网络拓扑结构产生机制的局部化.doc

无线传感器网络拓扑结构产生机制的局部化摘要无线传感器网络中需要的数据收集的基本拓扑结构是生成树，因为数据流主要是多对一的形式。网络中的节点可以通过两个阶段的处理自我设定成这样一个拓扑结构：所有节点的父类节点选择，根结点初始化能量流。我们展现了4种局部拓扑产生机制最早优先型，随机型，最近优先型以及随机有利的父类选择型。在如下参数：节点度数，强度，通道质量，数据集合以及反应时间，下对拥有这些机制的网络进行了比对。研究表明，不管自我成型的机制多么局部化，都会影响整个网络。关键词：无线传感器网络，父类选择，信息提取，生成树，集合树，局部/全局网络拓扑结构产生引言一个无线传感器网络实质上是节点的分布式收集，每个节点都有能力传感，计算，RF通信。在无线通信，计算以及MEMS技术的进步使生产廉价小巧的节点称为可能。我们可以想象在不久的将来，由数百或上千这些设备构成的无线传感器网络将应用在很多场合，如周围环境的监视，结构正常的监控，跟踪化学物质的意外漏出和溢出等1,5,10。在一些应用场合部署节点和事先设定好的拓扑结构是可能的，其他应用需要在边区或地区部署特别的无人的装置。我们考虑了在一些操作区部署了大量传感器节点的方案（例如，从一个空中媒介分散或垂直布置）。因为要求可测量性以及在边区或敌区的无人操作环境，这个传感器网络必须可以自我配置。这篇文章的首要集中点是网络拓扑结构的自我配置。在典型的多对一数据收集应用中，需要的基本传感器网络拓扑结构是生成树。这种树可以通过两个阶段的处理来建造：所有节点根据他们收到的信息选择父类节点，然后是发现信息后的数据流出量。注意到这个简单的树建造过程，完全局部化发挥了很大作用，导致了一个可以升级的设计。文章中，先描述了四种拓扑结构产生机制：最早优先型，随机型，最近优先型以及随机有利型。这些局部化机制的不同是父类节点选择占用了空间，导致了质量上不同的树结构。可以区分这些机制差别的一个重要的图形级别数据是节点度。接下来，我们在基于四种网络表现数据上：强度，通道质量，数据集合以及反应时间对四种机制进行了估算。主要不是找到最佳机制，因为，没有单一的战略对所有数据都表现的好。何况，我们的贡献是分析和评估不同的局部拓扑生成计划对全局网络性能的不同影响。文章的剩下部分安排如下：部分讨论了相关工作。部分介绍了在建造网络拓扑上的四种机制。部分讨论了用来评估的数据。部分提供了仿真的建立以及仿真结果。结论和工作展望在第部分。 相关工作在过去的几年中，我们从物理层上升到应用层等各个方面对传感器网络进行了实验。文章8总结了之前的研究，当前的协议工作以及在传感器网络中设计的算法。例如，12展现了一个新的MAC协议，4建议了一个以能量保留为目的的网络层协议。广播在无线传感器网络中是很常见的操作。广播最简单和最直接的方法是群发。11研究了广播风暴问题，表明群发很消耗能量，并导致严重的数据冗余，竞争和冲突。因为在拓扑结构建造开始时，只需要一个群发消息（以确保连通性），它的负面影响是可以忽略的。无线传感器网络中最重要的任务是信息提取。由于有限的能量资源，为了延长网络的寿命，这个数据收集处理一定需要节能。文章2模拟和分析了数据中心路由协议，表明由于数据集合的能量增益是很重要的，但可能导致较长的反应时间。本文中，我们着重于局部拓扑结构产生机制对网络影响的研究。其中的一些机制在6，7中首先提到，没有详细信息或估算。最后，需要确认的是，我们的目标集中在对网络的基本建造，因此，不要考虑象MAC这样的低能量水平协议。 父类选择战略在拓扑结构产生过程之前，在节点部署好后，基站（图1，2，3中的节点1）将群发发现的信息。根据第一时间收到的信息，每个节点将按图1（a）（b）（c）先后顺序重新传播群发信息。一个节点可能收到不止一个的群发信息，但它只选择更高能量水平的节点作为父节点。节点的能量水平，ID以及其他方面的信息被囊括在群发信息中，每个节点可以局部的提取，保存这些信息。因此，在群发之后，每个节点知道了即将相邻节点的信息，并根据这些信息进行父类选择。图1（d）给出了父类选择后的一个结果：节点4，5，6选择节点2作为他们的父类，节点2和3选择了节点1。在这个部分，我们展现了可以用来进行父类选择的4个局部化战略：最早优先型，随机型，最近优先型以及随机有利型。最早优先型父节点选择：这种模式下，每个节点将从最先收到群发消息的节点中选择一个作为父节点。这种模式执行起来最简单。一个传送群消息的节点首先将被它的下个能量等级（即到基站的距离有多个跳跃）的邻节点选为父节点。考虑到图2（a）的说明，可得节点2将比节点3更先传播，然后节点4，5，6都选择节点2作为父节点。图1.阶段：群发。这个阶段包括（a），（b），（c）。群发信息传播到整个网络。括弧中的数字表示候选的父节点；阶段：父节点选择。在群发后，每个节点根据一些父节点选择机制来从候选节点中选择父节点。（d）表明了一种可能结果。（d）中的实线表示被选的父节点，虚线表示其他可能的选择。图2.从基于拓扑结构产生机制的四种父节点选择方案可能结果的图解。a) 最早优先型 b)随机型 c)最近优先型以及d)随机有利型。随机型父节点选择：在这种模式下，节点将随机从可能的候选节点中等概率的选择它的父节点。节点5和6含有相同的父类候选节点，节点2和3，如图2（b）所解释的，他们做独立随机的决定。由于每个候选节点被选中的机会相等，传播的最快的节点将不再是唯一的被选节点。最近优先型父节点选择：节点将选择最近的候选节点来作为它的父节点。直观来讲，假设所有节点拥有相同的传送功率，这将在所有的连接中导致更好的通道质量。我们可以使用接收信号强度指示器（RSSI）来估计距离9。图2（c）解释了通过使用这种最近优先型战略来获得生成树。随机有利型父节点选择：这个模式下，每个节点根据它们的相邻节点数目分配一些重量到每个可能的父节点。父节点的选择根据这些重量是随机的。拥有多个邻节点的节点含有更少的重量，被选为父节点的可能性更小。在图2（d）中，节点2有5个相邻节点，节点3有4个相邻节点，因此，节点3拥有更高的重量，与节点2相比，被选为节点5和6的父节点的可能性更大。这种模式试图平衡每个父节点的子节点数目。参数在这个部分，我们描述了用来比较第部分描述的拓扑结构产生战略的5个指标，分别是：节点度，强度，通道质量，数据集合以及反应时间。节点度：即每个节点含有的子节点数，这是一种从理论图表来区别全局拓扑结构结果的方法。虽然这不是一个直接影响网络的参数，我们发现节点度的不同提高了在不同模式下拓扑结构的不同。强度：这个指标是在一个节点失败后，网络仍然连接的百分比。一个节点故障导致修复网络时额外的开销和临时中断节点。我们假设一个节点失败的概率与节点的使用情况有关。通道质量：随着信号传播时，无线电信号强度的衰落指数。表达式如下：其中，和分别代表接收点和传送点的信号强度。是接收点和传送点之间的距离，指数是一个环境决定的参数（在仿真中值为4）。下面我们定义通道质量是比特出错率。假设使用开关信号3，其中，是通道噪音的能量，在仿真中我们假设。图3.（a）和（b）表示数据集合，（c）和（d）表示两种不同树结构的反映时间。在图中A表示节点1渴望的信息，t1，t2，t3，t4代表传送发生时的时间，t1是最早的时间，t4是最晚的时间。这个数据表明，一个有更多聚类的树可能在数据集合上做的更好，但需要更多的反应时间。数据集合：如果一个事件发生，这个事件传感范围内的每个节点将发觉这个数据，并报告给根节点。因为在大多数情况下，每个节点将报告相同的信息，中间节点就可以排除冗余，使传送的数据量最小，因此保存能量。含有更多子节点的节点可以在集合上表现更好。在图3（a）和（b），如果节点4，5，6检测大同样的事件，并报告给节点1，数据汇总后传输的总数目和包含的节点集（1，4，5，6）2网络中含有最少节点Steiner树的边缘数目相等。在这种情况下，（a）的传送的总的节点数是4，(b)的为5。反映时间：我们假设有充足的通信通道来选择，每个节点只有一个无线电收发装置。因此，无线电收发机中多个单一节点对可以同时通信，但如果不止一个节点想要传送给同一个接收节点，传送信息必须为一次性传送。我们测量的反应时间是事件发生到根结点收到消息的总时间。例如，在图3（d）：在时间t1，节点4传送到节点2，节点6传送到节点3；在t2时刻，节点5到节点2，节点3到1；在t3时刻，节点2到1.因此，反应时间为3个时间单位。在图3（c）中，相似的反应时间为4。试验仿真和结果在之前的两个部分，我们描述了四种局部拓扑结构产生机制，五个用来评估他们的指标。这个部分将介绍仿真试验。在1*1的正方形区域，我们均匀的布置100个静态节点。网络中的所有节点有相同的通信范围R。根结点在低能量角落的左边，事件在网格空间的中心。定义感应距离为0.15，所以至少有3个传感器节点在这个事件的感应范围内。对信息提取的检测，数据集合，反应时间以及这些节点的所有数据都需要被收集并传递给根结点。我们一开始找到了连接网络的最小通信范围（Rmin），改变通信范围至2.5 Rmin。每种模式下的仿真都进行了平均20次。图4通过8展现了仿真结果。图4.节点度的变化：图中，当通信范围R增加（即节点密度更高）时，四种模式下节点度差异的不同也增加。图4表明了不同模式下节点度的不同。可以看出，当通信范围增加时，四种模式下节点度差异的不同也增加。最早优先型模式含有最高的变化差异，随机有利型的变化差异最低。图5.强度：一个节点失效后，至少仍有这一比例的节点连接到根结点的概率。图5表明了网络的强度。当通信范围大时，随机型和随机有利型比最早优先型和最近优先型更可靠。图6.通道质量图6表明最近优先型在所有四种模式下的比特出错率最低。这是因为最近优先型模式使用了高质量，短距离的连接。图7.数据集合图7表明以传送数量形式表现的数据集合需要报告一个事件。最早优先型和最近优先型模式比其他两种模式可以集合更多的数据，即可以保留更多的能量。图8.反应时间最后，图8展现了反应时间的结果。随机型和随进有利型比其他两种模式的反应时间要短，表明在这两种模式中有更快的信息提取速度。 总结与展望本文研究了局部拓扑生成机制对网络性能指标的影响。我们展现了四种机制最早优先型，随机型，最近优先型，随机有利型，以及一些评估他们的指标。通过仿真表明，局部化父类节点选择战略会以不同的方式影响全局网络的表现。总结我们的观察和仿真结果，发现最早优先型和最近优先型产生了数据采集树，在时间中具有低网络可靠性，高数据集合能力和较长反应时间的特点。此外，最近优先型在通道质量上比其他三种模式表现更好。在所有情况下，当通信距离大时（密度，每个机制因此可能的选择高时），网络性能的不同被极大的夸大了。另一个有趣结果是：从图7和8中，我们发现当时，需要传送的数据数量最小，四种模式的反应时间最短。这种结果值得进一步研究。在本文中，我们只考虑了由100个节点组成的网络。在今后的研究中，我们将分析更大规模的网络（如大于1000个节点），以及其他方式的节点布置。此文可以扩展的还有其他方面， 如为研究数据集合和反应时间，把其他丰富的模型相结合，以及对父节点选择方式的分析研究。参考1 A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, “Habitat Monitoring: Application Driver for Wireless Communications Technology,” 2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, Costa Rica, April 2001.2 B. Krishnamachari, D. Estrin, and S. Wicker, “The Impact of Data Aggregation in Wireless Sensor Networks,” In International Workshop on Distributed Even-Based Systems, Vienna, Austria, July 2002.3 B. P. Lathi, “Modern Digital and Analog Communication Systems,” third edition, Oxford University Press, Oxford, NY, 1998.4 C. Intanagonwiwat, R. Govindan and D. Estrin, “Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks,” Proc. of ACM MOBICOM00, August 2000.5 D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, “Next Century Challenges: Scalable Coordination in Sensor Networks,” Proc. of ACM MOBICOM99, Washington, August 1999.6 D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker, “Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks,” Technical Report CSD-TR 02-0013, UCLA, February 2002.7 D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker, “Large-scale Network Discovery: Design Tradeoffs in Wireless Sensor Systems,” Poster presented at the 18th ACM Symposium on Operating System Principles, Banff, Canada, October 2001.8 I. A