基于测量聚类的网络拓扑推断算法

为了减少基于端到端时延的拓扑推断算法中产生的测量流量,根据网络中端到端时延的特点,提出了一种测量聚类算法和两阶段拓扑推断算法.测量聚类算法在测量时首先粗略测量网络节点的端到端时延,根据时延对节点进行聚类,然后根据节点的聚类测量节点对的端到端时延并计算节点相关性,最后通过两阶段拓扑推断算法推断网络拓扑结构.理论证明了测量聚类算法能够有效减少测量产生的测量流量并通过NS2进行了仿真,仿真结果表明测量聚类算法和两阶段拓扑推断算法在有效减少测量流量的情况下能够正确地推断网络的拓扑结构.     

无线Mesh网络节点聚类属性分析

通过分析无线Mesh网络节点空间属性,提出了一种改进的k-medoids网络节点聚类算法.该算法基于聚类思想,将无线Mesh网络中的网关部署问题转化为空间节点数据聚类问题.构建了网络拓扑图的邻接矩阵,并利用邻接矩阵选择具有最多一跳连接节点数的对象作为初始簇中心.然后以网络跳数代替传统聚类算法中的距离参数,将最小化跳数之和作为优化目标,通过迭代方法获得稳定的聚类和分组结果.实验结果表明,离散的网络节点在空间上具有聚类特性,利用该方法可以获得更小的平均跳数和最大跳数,因此可以较好地实现网络节点分组和网关发现.     

基于往返时延的网络拓扑推断

为了减少拓扑推断中采用单向性能参数需要多个节点合作的限制,提出了一种基于往返时延的拓扑推断算法,设计了网络拓扑推断中的往返时延测量方法,基于往返时延的拓扑推断不需要时钟同步及目标节点的配合.从理论分析了基于往返时延推断网络拓扑结构的可行性和正确性,并通过NS2进行了仿真实验.仿真结果表明,基于往返时延的推断算法能够较准确地推断网络的拓扑结构,与基于单向性能参数的拓扑推断算法相比,基于往返时延的拓扑推断算法受到的限制较少.     

基于节点度数和跳数的网络检测点选取算法

为解决网络检测点的选取问题,基于网络节点度数和跳数信息,提出一种动态网络检测点选取算法. 该算法使用三元组信息标记网络节点,并通过比较和替换节点的三元组信息,根据三元组信息中参数N的不同取值,分别完成流量和延迟两种网络检测点的选取. 仿真结果表明,新算法不需要维护网络拓扑的全局信息,能够有效解决网络流量检测点和网络延迟检测点的选取问题.     

基于时延抖动的网络拓扑推断技术

为了克服基于端到端单向时延的拓扑推断算法中需要时钟同步的缺点,根据端到端时延抖动的定义和特点提出了拓扑推断中端到端时延抖动的四元分组列车测量方法和基于端到端时延抖动的拓扑推断算法,其中端到端时延抖动的测量不需要节点间的时钟同步,并且实现简单.分析了基于端到端时延抖动推断网络拓扑的可行性和正确性,通过NS2进行了仿真.仿真结果表明,基于时延抖动推断拓扑结构的效果比基于端到端单向时延推断拓扑结构的效果好.     

基于过滤器的K-NN深度优先查询算法

为减少数据查询的能量消耗,有效延长无线传感器网络的生存时间,提出了一种基于过滤器的K-NN深度优先查询(FKDF)算法.通过为每个节点设置过滤器来确定K-NN查询区间;利用查询节点的邻接表信息,在进行深度优先遍历时生成查询消息;基站分发查询消息,并等待查询节点返回查询结果,从而减少查询的平均跳数.仿真结果表明:与FILA设置过滤器方法和GPSR路由算法相比,FKDF算法节约了查询所需的平均跳数,能够适应网络拓扑结构的动态变化,当K值经常变化时不增加查询开销.     

动态拓扑推测的改进算法

为了在网络中有节点动态加入时推测更新的网络拓扑结构,提出了一种改进的逐步拓扑推测算法I-STIA。该算法首先计算新加入节点与网络中所有探测包接收节点之间的相关度,然后采用一个自适应的动态门限搜索加入节点在拓扑中的正确位置,并利用节点的TTL跳数信息减少搜索的步数。应用该算法可以有效地推测出更新的网络拓扑结构,并提高推测结果的准确度。仿真结果表明:I-STIA相比已有的算法更有效,在同等探测包数目情况下,推测结果的准确度更高。     

利用往返时延抖动的网络拓扑推断算法

为了克服基于端到端单向时延的拓扑推断需要时钟同步及节点间合作的限制,提出了一种利用往返时延抖动的拓扑推断算法.首先定义了四元组列车,其由4个长度相同的ping分组组成,4个ping分组组成2个相邻的紧接分组对,2个紧接分组对的目标地址相同.在空间独立性、时间独立性的条件下,通过四元组列车测量获得的往返时延抖动可以计算节点间的相关性,再根据节点间的相关性便可推断节点间共享链路,从而推断出网络拓扑.理论分析与仿真结果表明,所提算法的收敛速度高于基于端到端单向时延推断拓扑法,并且只需要一个测量节点.     

基于小世界现象的无线传感器网络拓扑优化

拓扑优化对提高无线传感器网络的性能具有重要意义,算法RLOC(Removing superfluous Linksto Optimize the Cluster)利用小世界现象对基于节点随机分布的无线传感器网络进行拓扑结构优化.RLOC算法基于对边的介数和集聚系数的分析,有选择性地删除一些多余的边.仿真表明此算法能够在保持整个网络连通的前提高下使网络拓扑结构简化,并显示出明显的簇结构,而整个网络平均跳数的变化不大.     

无线传感器网络自适应拥塞控制的路由算法分析

无线传感器网络中节点的覆盖范围有限,因而采用多跳路由传输方式.无线自组网中的多跳路由是由普通节点协作完成的,选择不同的转发节点,会对网络的信息传输产生不同的影响.对不同路由(洪泛路由、最短路径等)算法下的网络自适应拥塞控制进行了分析,研究了不同路由算法下的网络性能和拥塞控制效果.根据节点跳数与缓存占用的关系,提出一种基于节点跳数和缓存占用的性能函数的改进最短路径算法,算法选取使性能函数值最小的节点作为转发节点.最后,通过实验比较了最短路径算法与改进路由算法的网络性能,发现改进路由算法相比最短路径算法,具有较好的网络性能和服务质量.     

基于区域划分的DV-Hop定位算法的改进

DV Hop节点定位算法采用跳数乘以每跳平均跳距估算节点间的距离,而跳数和每跳平均跳距受网络的节点密度、节点的通信半径等参数影响较大。针对DV Hop算法存在的不足,提出一种基于跳数区域划分的DV Hop定位改进算法——HRDV Hop（Hop regional division DV Hop,HRDV Hop）。对一跳区域的节点测距引入RSSI技术,两跳或以上区域的节点采用跳数值修正法,再辅以限制跳数机制。MATLAB仿真测试结果表明,在相同的网络硬件和拓扑环境下,改进后的算法能更有效地降低节点间的距离估算误差,提高定位精度。     

基于迭代双通信半径的传感器网络DV-Hop算法

为了提高DV-Hop算法的定位精度,提出了一种基于迭代双通信半径的DV-Hop改进算法。首先针对当前网络拓扑结构选取一个合适的通信半径,并用它与节点的默认通信半径一起估计信标节点间的平均每跳距离,最后使用迭代算法对得到的平均每跳距离进行修正,选择误差最小的平均每跳距离对未知节点与信标节点间的距离进行计算。仿真实验结果表明,改进算法在不明显提高算法复杂度与通信量的基础上大大提高了定位精度。     

基于 RSSI 跳数连续的 DV-HOP 改进算法

针对经典DV-HOP(distance vector-hop)算法中节点间跳数信息对定位精度有较大影响这一问题,提出了一种基于接收信号强度指示(receive signal strength indicator,RSSI)的改进算法.该定位算法引入了连续跳数的定义,首先利用RSSI测距模型把直接邻居节点接收到的RSSI值转换为两节点之间的距离,再根据连续跳数的定义计算出两节点间的连续跳数.在相同的仿真网络环境里,与经典的DV-HOP算法相比,归一化定位误差降低了30％ ～ 45％;与其他改进定位算法相比,归一化定位误差也有不同程度的降低.仿真结果表明该改进算法大幅度地提高了定位精度.     

保证服务质量的最小能量无线传感器网络路由算法

为了减小无线传感器网络(wireless sensornetwork,WSN)的路由能量开销,同时保证数据传输的服务质量,提出了一种新的路由算法,称之为DEER(delay-constrained energy efficient routing)算法。DEER算法的核心思想是将路由选择和传输速率控制相结合。算法首先采用概率分析方法,估计出最优的总跳数以及相应的传输速率;然后再逐跳选择出后续节点,构成整条路径。理论分析和计算机仿真结果都表明,在现有的路由算法中,如果端到端传输时延变小,那么能量消耗将呈指数上升趋势;而在DEER算法中,二者的关系将从指数退化成多项式关系。可见,DEER算法不但保证了端到端传输的服务质量,而且大幅度地降低了路由能量开销。     

遗传算法的DV-Hop算法改进

DV-Hop算法中,平均每跳距离是影响定位精度的因素之一。针对平均每跳距离带来的定位误差,对锚节点和未知节点的平均每跳距离进行了改进和优化。首先引入遗传算法计算锚节点的平均每跳距离;然后利用跳数小于等于3的锚节点的平均每跳距离加权处理未知节点的平均每跳距离,减少平均每跳距离带来的误差。仿真结果表明,在不增加硬件开销的基础上,改进算法能够有效提高算法的定位精度,并且具有较好的稳定性。     

基于两跳邻居的ZigBee网络借地址分配算法

针对标准DAAM算法可能产生网络深度折回问题及父节点可分配的地址空间分布不均,提出一种基于两跳邻居的ZigBee网络借地址分配算法。通过控制子节点发送地址请求信息的监测范围设为两跳通信距离内的邻居节点,并改进实时路由,实现优化网络拓扑结构,减少孤立节点。理论和仿真分析表明改进算法在地址分配成功率,地址分配平均耗时等方面优于DAAM算法。