传感网中的动态Delauanay三角剖分算法

几何路由协议受益于局部Delaunay三角剖分，因为Delaunay三角剖分可以保证消息转发的可达性和限制路由长度的界。本文提出一种构造无线传感网中Delaunay三角剖分的局部算法。此算法不但考虑了静态情况，而且考虑了允许节点动态地加入和退出网络的动态情况。在静态情况和动态情况下，算法的通信开销都是O（nlogn）位。因此，此算法
法可以应用于节点可以动态加入和退出的无线传感网。本文还证明了算法的正确性。     

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

用随机增量局部转换算法实现三维点集的Delaunay三角剖分

Delaunay三角剖分作为计算几何中的一个核心问题,尤其适用于三维网格生成.因此就需要开发出高效、健壮性的算法来实现.本文在原有算法的基础上提出了随机增量局部转换的算法来实现三维点集的Delaunay三角剖分.采用不退化的四点生成最初的三角剖分,每次加入一点,通过局部交换使新的三角剖分保持Delaunay性质,直到处理完所有点.还讨论了局部交换的思想和对不同面类型的处理方法,给出了两个剖分实例.     

无线传感器网络中的分布式平面t-支撑拓扑控制算法

在确保无线传感器网络连通的前提下,每个节点自适应地调整自己的发射功率,通过最小化节点的能耗和减少节点间的通信干扰,达到延长网络生存时间的目的.基于 Voronoi划分和局部Delaunay三角剖分,提出一种新的几何结构PSLDel图(planar symmetric local Delaunay triangulation)以及其分布式构造算法,为无线传感器网络建立连通、稀疏、平面、t-支撑的底层逻辑拓扑,每个节点将依据最远的逻辑邻居调整到最小发射功率.仿真实验表明,PSLDel图在逻辑邻居、最小发射功率和通信干扰等性能方面接近集中式构造的UDel图,而且PSLDel图的网络延迟稍微优于 UDel图;与分布式构造的AUDel图相比,PSLDel图的通信开销至少可以降低55%,从而有利于提高无线传感器网络的能量使用效率.     

基于Delaunay三角剖分的有向传感器网络覆盖增强算法*

针对视频传感器网络的区域覆盖问题,提出一种基于Delaunay三角剖分思想的几何算法,选取围绕传感器的具有最大面积的Delaunay三角形重心作为决策方向。在此基础上,将Delaunay三角剖分的几何方法与分布式贪婪算法进行了融合,引入“贡献率”概念反映节点在其候选方向上可能覆盖区域的大小,以解决冗余覆盖的问题。仿真结果证明了该算法的有效性。     

基于EMST的平面点集Delaunay三角剖分

提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率.     

Delaunay三角剖分的节点模糊信息三维定位方法

为了有效提高三维空间中无线传感器网络节点定位算法的效率,提出了一种基于简单Delaunay三角剖分的模糊信息节点定位方法(Fuzzy Information Node Localization on Delaunay Triangulation,FINL-DT),该方法在定位前先对网络中的锚节点实现Delaunay三角剖分,然后通过测量各三角形中锚节点与未知节点的方向角和俯仰角实现节点定位。每一轮定位结束后,判断并更新无效锚节点的位置。网络中的节点被定位后充当二级锚节点辅助定位其他节点。通过实验仿真,与SLPM-FI算法和3D-ADAL算法相比,FINL-DT算法提高了节点定位精度,降低了网络能耗。     

任意多边形Delaunay三角剖分改进算法

本文重点研究任意多边形的Delaunay三角剖分,研究发现现有常用任意多边形Delaunay三角剖分存在执行效率低、候选节点可能出现"位置违约"错误等缺陷,根据候选节点与当前边夹角的大小关系,本文提出一种基于有向边的任意多边形Delaunay三角剖分改进算法,该算法具有执行效率高,避免了现有常用算法中可能出现"位置违约"的错误,完善了原算法的健壮性.     

无线传感器网络中基于Voronoi覆盖及Delaunay三角剖分图的最小刚性拓扑控制算法

为同时满足覆盖与节能应用需求,本文提出了无线传感器网络中一种最小刚性拓扑控制算法MRTc（Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation）.该算法基于Voronoi覆盖机制,准确控制节点工作状态,实现活动节点对目标区域的完全覆盖.在此基础上,MRTc利用Delaunay三角剖分图的特点,构建出适用于无线传感器网络的最小刚性拓扑结构.该结构有效约束了网络平均节点度,且同时具有容错性、覆盖性和稀疏性.此外,MRTc引入节点功率控制策略,在维持网络完全覆盖的基础上最小化节点能耗.仿真结果进一步验证了本文提出的MRTc算法的有效性.     

点云的形状与曲线重建算法

针对平面无序带噪点云的曲线重建问题,给出了点云形状的定义并提出了构造点云形状的算法.该算法基于Delaunay三角剖分,在构造好点云的Delaunay三角剖分后对三角剖分进行细化,使得在点云中的点周围形成空间上的局部均匀采样;基于集合论中的基本概念定义点云中内点、外点和边界点,并且明确地定义了点云的形状,根据Delaunay三角剖分细化时,选择不同的参数得到不同层次的点云的形状;选择合适的参数得到相应形状后,通过薄化过程得到具有流形结构的曲线.实验结果表明,采用文中算法得到的重建曲线很好地反映了点云的形状,验证了该算法的有效性.     

Localized Delaunay triangulation with application in ad hoc wireless networks

Several localized routing protocols guarantee the delivery of the packets when the underlying network topology is a planar graph. Typically, relative neighborhood graph (RING) or Gabriel graph (GG) is used as such planar structure. However, it is well-known that the spanning ratios of these two graphs are not bounded by any constant (even for uniform randomly distributed points). Bose et al. (1999) recently developed a localized routing protocol that guarantees that the distance traveled by the packets is within a constant factor of the minimum if Delaunay triangulation of all wireless nodes is used, in addition, to guarantee the delivery of the packets. However, it is expensive to construct the Delaunay triangulation in a distributed manner. Given a set of wireless nodes, we model the network as a unit-disk graph (UDG), in which a link uv exists only if the distance /spl par/uv/spl par/ is at most the maximum transmission range. In this paper, we present a novel localized networking protocol that constructs a planar 2 5-spanner of UDG, called the localized Delaunay triangulation (LDEL), as network topology. It contains all edges that are both in the unit-disk graph and the Delaunay triangulation of all nodes. The total communication cost of our networking protocol is O(n log n) bits, which is within a constant factor of the optimum to construct any structure in a distributed manner. Our experiments show that the delivery rates of some of the existing localized routing protocols are increased when localized Delaunay triangulation is used instead of several previously proposed topologies. Our simulations also show that the traveled distance of the packets is significantly less when the FACE routing algorithm is applied on LDEL, rather than applied on GG.     

无线传感器网络的RPL路由协议研究

路由协议执行网络拓扑描述、路由选择和数据包转发的功能,影响整个网络的性能和存活时间。现有的路由协议需要发送大量数据包维护网络拓扑,以及大量的存储空间来存储路由条目。由于硬件的限制,无线传感器节点无论是能量,还是其处理能力、存储能力都受到极大的制约。因此,IETFRoLL工作组提出了一种针对低功耗有损网络的IPV6路由协议,即RPL路由协议。文中对RPL路由协议的拓扑构建过程、数据包路由过程和Trickle定时器的算法等进行了分析,通过使用COOJA仿真工具对其进行仿真,验证了RPL路由协议在低功耗有损网络中具有较高的性能。     

一种适用于无线传感器网络的拓扑控制算法

无线传感器网络拓扑控制算法对于延长网络的生存时间、减小通信干扰、提高路由协议和MAC协议的效率等具有重要的意义.在分析XTC(eXemplary Topology Control)算法的基础上,提出一种改进的基于局部网络信息的分布式拓扑控制算法M-XTC(M0dIfied-XTC).改进算法保持了XTC算法简单、实用,不需要节点位置信息,适用于普通节点、异构网络和三维空间等优点,并且更有利于延长网络的生存时间,具有更好的实时性和鲁棒性.     

基于SASR的多路径协议SAMSR研究

比较和分析了自组网络中单路径与多路径的反应式路由协议,在SASR的基础上提出了一个新的多路径路由协议SAMSR。它通过记录重复的RREQ报文以获得更多网络拓扑信息,从而发现更多的可达路径,以及在收到重复的RREP报文后,发回重选报文RSEL保证路径间的节点不相干性。最后通过在NS-2平台上模拟考查其性能,表明SAMSR协议虽然增加了网络开销,但提高了分组抵达率,减少了端到端的路由时延。     

A new algorithm for packet routing problems using chaotic neurodynamics and its surrogate analysis

We propose a new algorithm for routing packets which effectively avoids packet congestion in computer networks. The algorithm involves chaotic neurodynamics. To realize effective packet routing, we first composed a basic method by a neural network, which routes packets with shortest path information between two nodes in the computer network. When the computer network has an irregular topology, the basic routing method does not work well, because most of packets cannot be transmitted to their destinations due to packet congestion in the computer network. To avoid such an undesirable problem, we employed chaotic neurodynamics to extend the basic method. Numerical experiments show that our proposed method exhibits good performance for scale-free networks. We also analyze why the proposed routing method is effective, comparing the proposed method with several stochastic methods. We introduced the method of surrogate data, a statistical hypothesis testing which is often used in the field of nonlinear time-series analysis. Analysis of the proposed method by the method of surrogate data reveals that the chaotic neurodynamics is most effective to decentralize the packet congestion in the computer network.     

A learning automata-based fault-tolerant routing algorithm for mobile ad hoc networks

Reliable routing of packets in a Mobile Ad Hoc Network (MANET) has always been a major concern. The open medium and the susceptibility of the nodes of being fault-prone make the design of protocols for these networks a challenging task. The faults in these networks, which occur either due to the failure of nodes or due to reorganization, can eventuate to packet loss. Such losses degrade the performance of the routing protocols running on them. In this paper, we propose a routing algorithm, named as learning automata based fault-tolerant routing algorithm (LAFTRA), which is capable of routing in the presence of faulty nodes in MANETs using multipath routing. We have used the theory of Learning Automata (LA) for optimizing the selection of paths, reducing the overhead in the network, and for learning about the faulty nodes present in the network. The proposed algorithm can be juxtaposed to any existing routing protocol in a MANET. The results of simulation of our protocol using network simulator 2 (ns-2) shows the increase in packet delivery ratio and decrease in overhead compared to the existing protocols. The proposed protocol gains an edge over FTAR, E2FT by nearly 2% and by more than 10% when compared with AODV in terms of packet delivery ratio with nearly 30% faulty nodes in the network. The overhead generated by our protocol is lesser by 1% as compared to FTAR and by nearly 17% as compared to E2FT when there are nearly 30% faulty nodes.     

An Energy-Aware Geographic Routing Protocol for Mobile Ad Hoc Networks

Mobile ad hoc networks (MANET) are characterized by multi-hop wireless links and resource constrained nodes. To improve network lifetime, energy balance is an important concern in such networks. Geographic routing has been widely regarded as efficient and scalable. However, it cannot guarantee packet delivery in some cases, such as faulty location services. Moreover, greedy forwarding always takes the shortest local path so that it has a tendency of depleting the energy of nodes on the shortest path. The matter gets even worse when the nodes on the boundaries of routing holes suffer from excessive energy consumption, since geographic routing tends to deliver data packets along the boundaries by perimeter routing. In this paper, we present an Energy-Aware Geographic Routing (EGR) protocol for MANET that combines local position information and residual energy levels to make routing decisions. In addition, we use the prediction of the range of a destination''s movement to improve the delivery ratio. The simulation shows that EGR exhibits a noticeably longer network lifetime and a higher delivery rate than some non-energy-aware geographic routing algorithms, such as GPSR, while not compromising too much on end-to-end delivery delay.     

基于最近社交圈的社交时延容忍网络路由策略

无稳定拓扑使时延容忍网络(delay tolerant networks,DTN)路由协议主要通过增加冗余数据包副本提高路由性能.社交网络是DTN的一种典型应用场景,但由于其网络规模相对较大,当网络负载高时,通常的DTN路由不能有效控制数据包副本的数量,从而产生大量丢包导致性能下降.借鉴MANET网络中利用分簇结构控制网络冗余路由数据包的思想,通过分析社交网络中节点的移动模型,定义了在社交关系的约束下,聚合移动规律相近的节点构成最近社交圈的节点簇组成策略.提出了一种基于该分簇结构的分为簇外喷射、簇间转发和簇内传染3个阶段的社交时延网络路由协议.实验证明,这种基于最近社交圈分簇结构的路由能有效地控制冗余数据包副本的产生,并在高网络负载的情况下仍然能够达到较好的性能.     

A cost matrix agent for shortest path routing in ad hoc networks

Wireless ad hoc networks do not rely on an existing infrastructure. They are organized as a network with nodes that act as hosts and routers to treat packets. With their frequent changes in topology, ad hoc networks do not rely on the same routing methods as for pre-established wired networks; they require routing methods for mobile wireless networks. To select a path from a source to a destination in dynamic ad hoc networks, an efficient and reliable routing method is very important. In this paper, we introduce a cost-matrix-based routing algorithm. An agent node creates topology information in the form of the adjacency-cost matrix which shows link costs of the network.Based on the adjacency-cost matrix, the minimum-cost matrix and the next-node matrices can be calculated. Based on the minimum-cost matrix and the next-node matrices, the minimum cost between source and destination nodes and between intermediate nodes on the minimum-cost paths can be calculated.The matrices are periodically distributed by the agent to the other nodes. Based on the minimum-cost matrix and the next-node matrices, each node decides the minimum-cost path to its destination. Because none of the nodes except the agent needs to gather network topology information, the control overhead of the proposed method is small compared with those of the general table-driven routing protocols.