论文部分内容阅读
传感器网络的分区是指:通过分割,将一个网络划分为多个凸区域。本文提出了一种新的基于Morse函数的分割算法,利用传感器网络的Reeb图知识进行凸区域分割。在分割联通的大型2D/3D传感器网络时,本文提出了名为CONSEL的可扩展分割算法。具体的步骤包括:首先,几个边界节点会进行洪泛,构造Reeb图。然后,普通节点根据洪泛过程中记录下的跳数信息,计算本地的互斥对,从而完成网络粗分割。接下来,非互斥对的相邻区域互相合并。最后,通过忽略凹度较小的互斥对,CONSEL提供更精确的网络分割。与以往的研究相比,CONSEL有如下优势:(1)可以用于二维和三维传感器网络;(2)只依赖于网络连接信息;(3)CONSEL可以对所有分割区域设置凹度上限,从而控制凸分解的精度。大量的仿真结果表明,CONSEL运作良好,无论洞和网络形状如何变化,始终可以得到合适的分割结果。 此外,现在很多实际场景中,3D传感器网络都是部署在复杂的3D空间中的,比如矿井,海底隧道,大楼走廊等等。这些3D传感器网络的拓扑结构和高属的3D表面是拓扑同构的(这里高属是指网络拓扑存在多个环路)。现有的平面映射算法不能把这样的网络拓扑映射到一个简单平面拓扑上,因此贪婪路由难以实现。为了解决以上问题,在本文中,我们提出了一种新的可扩展的分布式平面映射和路由算法,称为SINUS。SINUS实现的步骤如下:首先,根据Morse理论和Reeb图,找到高属表面拓扑的最大割集。通过此割集将高属表面切割成一个属0的(存在0个回路的),有2n条边界的表面。然后,将这2n条边界分成两组,通过一个类似深度搜索的算法将每组的边连接起来。这样,即形成了一个只有两条边界的属0表面。最后,利用Ricci流算法和Mobius变换,可以将有两条边界的属0表面映射到一个平面的环形带。通过平面的环形带节点的虚拟坐标,SINUS最终实现了使用本地路由决策的贪婪路由。模拟结果显示,SINUS在保证路由成功的同时,实现了较低的路由伸长度,并且平衡了路由的流量负载。