无线代理传感器网络的小世界效应080220116 侯永涛译摘要覆盖面，允许的出错率和能量消耗， 这些限制给移动式传感器或其它移动代理器 的最佳布置带来一个很大的难题。 移动代理器或传感器设备的这种特殊的物理层 布置可抽象为覆盖图， 为了描述和分析它们， 我们发展了一个模型。 这些设备的 平面图通常可用小世界网络的 “捷径”进行定义； 由此形成的网络特性则介于固 定的规则网格图和随机的平面图之间。 利用计算物理的一些方法包括逾渗和尺度 效应现象得到的各种各样的结果可用来解释这种网络的特性。 个人移动设备可利 用欧几里德空间的点和受它影响的简单圆区域来表示； 团簇的运算方法可用来建 立连通图， 利用典型图论处理方法就可进行分析。 我们描述了一些由特殊的几何 网络排列方式而产生的小世界效应，利用它们可以改善传感器网络的覆盖方式， 允许的出错率以及使用寿命。关键字： 无线代理器 小世界网络 尺度效应 逾渗 最优化覆盖1引言Ad-hoc 网络是一个重要和活跃的领域， 随着各种平民价格配置设备的广泛应用， 比如个人数字助理（掌上电脑）和其它移动代理或设备， ad-hoc 网络有了许多 新的应用。然而这令人乐观的 ad-hoc 网络仍存在许多不小的问题，比如设备成 本，性能和可靠性。 近来人们对小世界网络效应的兴趣集中在用来分析网络系统 的图论和尺度效应理论的适用性问题。 这篇论文中我们描述了一些新颖的涉及到 小世界网络效应的 ad-hoc 网络情形，展示了“捷径”对 ad-hoc 网络行为和特性 的影响。Ad-hoc 网络的关键属性是决策点的布置，即关于参与点的位置和体系。传统的 基于代理器的系统只具有本地信息， 只能获取部分或已过时的全局信息。 例如手 上电脑用户在移动过程中就受到不能达到网络的最优化连通或覆盖的因素的影 响，他们对代理器的布置或许也缺乏图论的相关知识。在第二节中我们描述了一些应用场合， 在这些情形中移动代理器或传感器能从小 世界网络近似中获益。 三，四节中介绍了如何用图论计算网络连通性问题， 第五 节介绍了怎样将小世界捷径影响整合进模型中。 六，七节中我们讨论了将模型拓 展应用于不对称移动设备的代理器操控和无规则的失效设备的一些方法。2应用场合Ad-hoc 网络产生于很多情况，包括民用的，军用的，医学的，传感器应用。我 们把这些情形下的组件模拟成离散的代理器， 尽管它们在某一特定任务中并没有 协同操作，但它们有着相似的目标。 膝上型电脑和个人数字助手的移动用户在他们的工作区有典型的无线网络覆盖。 日用定价的无线网络如 IEEE 802.11b 和相关标准在一些工作环境中已相当普 遍，他们通常雇佣基站天线系统。 即使当基站覆盖无效了， 利用点对点原则对节 点进行操作仍然有效。 这在许多掌上电脑或膝上型电脑网络中可行， 通过短程传 输技术如红外设备或最近兴起的短程无线技术如蓝牙技术即可实现。 这两种技术 都支持点对点的交流通常在视线范围内或最好在听力范围内的设备之间。 支持膝上型电脑和掌上电脑之间较高带宽的点对点交流的主要障碍是， 它没有较 高层管理和组织协议来建立 ad-hoc 网络中移动节点间的关系。通过像我们讨论 的一体化的网络，管理层决策可在每个对等的节点上来进行处理。 军事应用涉及到个体作战单位 （步兵或车辆） 的布置， 它们或许有一个最初的布 置形态但是必须适应时刻改变的外部环境。 一个比较近的想法是医学方面的“灵敏的灰尘” ，通过它小型设备可扩散进身体 用来记录和报道潜在的信息。 通常这些设备寿命很短， 信息传送距离很小， 我们 可以构建一个 ad-hoc 传送网络进行信息交流，通过中转将它们的数据传到唯一 的交流控制点，比如肉眼可见的医学探针。 其它应用包括基于代理的传感器的布置， 用来记录天气状况， 测量或建立控制数 据，用一个自洽的 ad-hoc 网络布置远比用传统的基于光纤的系统划算的多，光 纤系统还要事先计划好大量物理细节。移动设备要解决的一些具体操作是： 多次传播和广播涉及到在已知的参与节点的 子集或全部集合之间的交流； 地理测绘涉及到在目标地理区域偶然遇到未知节点 子集之间的交流。 大量应用情形来自特殊布置和重新布置的要求。 在军事上， 布 置设备时能够指定最初的布置模式以达到特定地区的覆盖。 通常它的建立也需要 军事策略，以便随着军事任务的进展及时重新进行布置。某些节点可能会失效， 地面环境可能发生变化， 甚至总带宽要求也可能变化， 这些都要求节点要么物理 位置进行变动要么以不同的行为来适应环境的动态变化。 一个有趣的实际要求是要尽可能好地利用提供给单个节点的通常有限的能量。 一 般来说节点利用较低的能量供应只能维持较小的地区覆盖和较窄的与其它节点 交流的带宽。 高的能量输出就要求增加覆盖和带宽。 一个节点可以采用混合策略 转变为高能量形式与它临近的节点建立联系或者在 “可信任模式” 下发送 超过它能够发送的更大数据量。在一个坏节点附近的节点可以通过改变自己的行为来补偿它， 可作为路由器或者 处理更大的范围或带宽来填补因坏节点产生的空白。对于模型必须利用本地化策略来说这些问题非常有趣。 假设问题的本质是节点可 能暂时分离或是超出管理控制器的范围如果要表现的和好的节点一样则它 们需要深入的本地信息策略。我们试图发展出一个全面的模型能够处理上面描述的所有应用场合。 通常面临的 一些问题是： 最初的和最终的布置形式； 布置环境的特性和特征； 技术的美妙与 简洁和系统成本之间的经济与权衡问题。最初的布置模式可能是涉及简单计量几何学的规则模式。 网格和网孔是熟知的工 具，对于较小的节点失效来说通常比较稳定。 随机网络来源于移动用户实际中的 无关联运动。 小世界网络的思想由 Watts 和 Strogatz 创造，它为我们找到了一个 利用可计量参数来研究介于这两种极限之间的网络的方法。3. 代理器的图解计算这节中我们用图解方法对移动设备的 ad-hoc网络进行计算。关于这个问题的一个标准图解方程是连通图的表示G=G(V E),其中V代表顶点集或移动传感器代理，E代表连接一对节点的边的集合。我们用符号NV-|V|代表系统中移动节点的数量。当节点彼此在连通领域内外移动时，模型通常要求与 时间t强相关E=E(t) o如果我们通过使节点失去能量的方法来使某些节点失效， 那么V=V(t)中|V|是一个随时间单调减小的函数。实际过程中，会有新的节点来 弥补那些旧的失效节点。图G由空间分布的NV个节点构建。我们的模拟模型是关于单位面积的快速计算， 在这个单位面积中节点是根据某一布置模式或策略布置的。单位面积的选择使我们有效地将目前模型中的距离和密度标准化。最简单的布置策略是均衡的随机分布。由此产生的随机图可以作为很好的参考 点，与其它更复杂模式产生的连通性和其它属性进行比较。可以设想空中降落的传感器，本质上就是一个随机分布，在降落过程中受到风吹和其它不可预见不可 控制因素的影响。一个简单的构建图的边集合的方法是假设每个传感器为一个传送半径为R接收半径为R的圆。这篇论文中我们考虑接收和传送距离均相等的对称情况，由此 产生的连通图为非定向(边包含成对的定向弧)。我们这里只考虑涉及简单几何 学的有限模型，不考虑外部的环绕对所选单位面积的影响， 所以该模型只有内部 效应和边界效应。从盖然性角度考虑，在分布面积边界的节点比深入内部的节点 本质上是“较少连接的”图一：单位面积中，相互影响的 loo个圆区域节点半径分别为 0.080,0.099,0.150 和 0.180图一向我们展示了一组不同灵敏度半径或交流范围的移动设备在单位面积中的 随机分布图。在彼此间交流范围内的节点由一条边连起来。小半径的图基本是离散的，包含大量小的簇并且大量的单个节点完全处于孤立状态。随着交流半径的增大，这些簇开始相互连接，渐渐地当达到半径的逾渗临界点时，系统变得只有一个连通图或者说一个簇。在这一临界点时，任意两点之间都会由一条路径连通。我们可以研究更多特殊的布置形态。人们或许会本能地期望找到一个理想的可弥 补圆形缺陷的栅格布置以达到最佳覆盖一一六边形格子就很有效，它能以最紧凑的方式包围圆形传感器。对于被包围的模型或者栅格布置在理论上无限重复，具有无限数量传感器的模型，我们能够获得它们的解析解。实际操作中，对于给定 分布模式的多种结构，我们可以利用蒙特卡洛采样方法计算出一个有用的覆盖 率。当整个系统图G完全连接起来时，我们会对它越来越感兴趣。这种情况下每个传 感器代理都能找到一些路径到达其它任何节点，但在接近完全连接的极限情况 下，流量负载很难达到平衡，一些节点对维持系统连通性会至关重要。 小于连通 极限情况下，系统碎片会聚集起来或成为有连通性的孤岛。 这可以用数学中的簇 或最小生成树法则进行定义。用簇对模拟系统进行计量很有效，即使图没有完全 连接，我们也可以对它的连通距离进行合理的解释。即使在一个完全连接的单簇系统中，连接节点间的路线也并不是所要求的最优化 的。在半径变量的某个取值范围内，会出现这种情况，即有某些节点是非常重要 的“热点”，它们对簇的连通性至关重要。T _ -1C310 051I* 1 I111 p 1 1J7JIj-N1 Mtj-iwfiso.wr =牛O.C1191函aw調斥咗軍isr图2 :单位面积中，由N个圆区域组成的簇中（N取值不同）随感知半径变化的所有节点对的平均距离通过测量簇中独立的成对节点间的距离分布，我们能进一步研究节点的行为特 性。对整个系统中所有节点对求平均距离就是一种测量方法。图2展示了 100个相互独立的系统在Nz分别取100，300, 1000时所有节点对的平均距离取值。 当感知半径较大时，所有的节点都可以看到彼此并且所有节点对的平均距离趋于 一致。减小“可视半径”会引起所有节点对平均距离的增大，事实上在某一点平 均距离会达到极大，这一点的位置由有限的节点簇的大小决定。我们计算每个簇 中所有的内部节点对，就不会得到发散的结果或分离的系统， 这样的结果保持有 限并且为簇内部提供了一个很有意义的平均值。 在对数坐标系所显示的曲线下降 和指数尾部是由系统分裂成许多小的簇所致。当系统变得很不连续时，所有节点对平均距离最终下降为噪声，事实上在很小的感知半径下单个节点是相互分离 的。对于较小的感知半径，较大的系统会保留一些连通属性。1P1 V V,hJ r i |4i r i ifl1H k 1 1 1 Y11L.BOCHO&1M1图3 :单位面积中，圆区域节点数量N不同，随感知半径变化的簇的数量图3展示了系统中相应的簇的数量。数据以临界半径为界而具有不同的特征，这个临界值与用密度表征的移动传感器节点的数量相关，小于它时系统分裂成具有 连通性的孤岛，大于它时系统完全相连。半径很小时系统退化成N个独立的代理传感器，它们之间不能相互联系。在这一点得出的系统属性正是只依赖于它们 自己位置的单个节点的属性。将数据画在对数-对数坐标系中就会发现当簇数量* * 、小于R时曲线呈现稳定的对数衰减（R是保证系统连通性的临界值一一图中显 示它的值接近0.1 ）。对较大系统来说状态转变比较剧烈，较大采样范围和较大 型系统的误差锯齿线会相应地缩短一一误差锯齿线显示了100个不同例子的平均变化情况。4. 图的分析这篇论文中我们所作的工作是利用严格的数学方法计算所有节点的平均距离和簇大小的分布。用于测量的计算方法是