Distributed load balancing mechanism for detouring schemes of geographic routing in wireless sensor networks

Well-known ‘routing hole’ problem of geographic routing is hardly avoided in wireless sensor networks because of various actual geographical environments. Existing geographic routing protocols use perimeter routing strategies to find a detour path around the boundary of holes when they encounter the local minimum during greedy forwarding. However, this solution may lead to uneven energy consumption around the holes since it consumes more energy of the boundary sensors. It becomes more serious when holes appear in most of routing paths in a large-scale sensor network. In this paper, we propose a novel distributed strategy to balance the traffic load on the boundary of holes by virtually changing the sizes of these holes. The proposed mechanism dynamically controls holes to expand and shrink circularly without changing the underlying forwarding strategy. Therefore, it can be applied to most of the existing geographic routing protocols which detour around holes. Simulation results show that our strategy can effectively balance the load around holes, thus prolonging the network life of sensor networks when an existing geographic routing protocol is used as the underlying routing protocol.     

Impact of sensing coverage on greedy geographic routing algorithms

Greedy geographic routing is an attractive localized routing scheme for wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks (e.g., surveillance or object tracking systems) that provide sensing coverage over a geographic area. Our analysis and simulation results demonstrate that an existing geographic routing algorithm, greedy forwarding (GF), can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under GF. We also propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that achieves path dilation lower than 4.62 in sensing-covered networks as long as the communication range is at least twice the sensing range. Furthermore, we extend GF and BVGF to achieve provable performance bounds in terms of total number of transmissions and reliability in lossy networks.     

Geographical Cluster-Based Routing in Sensing-Covered Networks

The relationship between coverage and connectivity in sensor networks has been investigated in recent research treating both network parameters in a unified framework. It is known that networks covering a convex area are connected if the communication range of each node is at least twice a unique sensing range used by each node. Furthermore, geographic greedy routing is a viable and effective approach providing guaranteed delivery for this special network class. In this work, we will show that the result about network connectivity does not suffer from generalizing the concept of sensing coverage to arbitrary network deployment regions. However, dropping the assumption that the monitored area is convex requires the application of greedy recovery strategies like traversing a locally extracted planar subgraph. This work investigates a recently proposed planar graph routing variant and introduces a slight but effective simplification. Both methods perform message forwarding along the edges of a virtual overlay graph instead of using wireless links for planar graph construction directly. In general, there exist connected network configurations where both routing variants may fail. However, we will prove three theoretical bounds which are a sufficient condition for guaranteed delivery of these routing strategies applied in specific classes of sensing covered networks. By simulation results, we show that geographical cluster-based routing outperforms existing related geographical routing variants based on one-hop neighbor information. Furthermore, simulations performed show that geographical cluster-based routing achieves a comparable performance compared to variants based on two-hop neighbor information, while maintaining the routing topology consumes a significantly reduced amount of communication resources.     

Position-based routing in vehicular networks: A survey

Routing in vehicular network is a challenging task due to network partitioning, high vehicular speed, and city environment characteristics. These characteristics results in degraded performance in traditional routing protocols. Traditional routing protocols, addressing the issues of mobile ad hoc network, are applicable for MANET applications. Position-based routing protocols, which are mostly based on greedy routing, are more suited to highly dynamic and mobile network. In this paper, we survey state of art routing protocols previously used in vehicular networks, present open research challenges and possible future direction. We categorize protocols into two categories based on their communicating mode (vehicle-to-vehicle, vehicle-to-infrastructure) irrespective of their simulating environment (highway, urban). Both vehicle-to-vehicle and vehicle-to-infrastructure communication provides connectivity based on multi-hop paradigm in a seamless way. We discuss pros and cons for routing protocols belonging to each category. By doing qualitative comparison of routing protocols, it is observed that hybrid communication would be the better choice for both communication mode operable in either a city environment or an open environment.     

贪婪协议路由代数及其应用

在无线网络路由协议中,错误地使用路由尺度会降低网络的路由性能,甚至会导致某些节点之间根本无法正常通信,称为路由尺度的兼容性问题.基于路由代数理论,分析了贪婪协议中路由尺度的兼容性问题,推导出了贪婪算法用作数据分组的转发机制时贪婪协议具有可达性的充分必要条件,并以4个路由尺度实例说明了分析结论在贪婪协议设计中的具体应用,为贪婪协议的设计提供了重要的技术依据.     

无线传感器网络中分段贪婪地理路由算法

针对基于地理位置的无线传感器网络路由中存在的路由空洞问题,提出一种新的路由模式:分段贪婪路由.在该模式中,整个路由过程被中间节点序列划分为若干段,在每一段上仅应用贪婪转发策略.为确定合适的中间节点,给出一种基于递归探测的方法,并以GPSR算法为基础探测路由构造了SGR算法.仿真实验表明,在存在不同类型、大小、数量路由空洞的网络环境中,SGR算法均能以较小的探测开销获得接近最优的路由路径,尤其是凹空洞存在的情况.     

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.     

多跳无线移动Ad Hoc网络路由协议的研究分析

无线移动Ad Hoe网络(MANET)作为可移动分布式多跳无线网络，没有预先确定的网络拓扑或网络基础设施以及集中控制．为了在如此的网络中促进通信，路由协议主要用于在节点之间发现路径．Ad Hoe网络路由协议的主要目的是网络拓扑的动态变化、任意两个节点之间建立一个使得通信总费用和带宽消费最少的正确和有效的通信路径．描述了设计移动Ad Hoe网络路由协议所面临的问题以及对它们的评价，详细比较了七种典型无线移动AdHoe网络路由协议的特性和功能，即DSDV，CGSR，WRP，AODV，DSR，TORA和ABR，为进一步的研究提出了新的课题．     

MANET路由协议研究进展

MANET（mobile ad-hoc network)是独立的网络自治系统，不依赖于固定主干网（但可以与其配合），该系统能快速部署到位，建立起一套完整，强大，高抗毁的网络通信系统，提供有效的数据和多媒体通信服务，MANET使用无线通信技术，所有主机均可以移动，主机间以无线链路连接，为了进行有效通信，必须在移动主机间建立合适的路由，回顾了MANET路由技术的研究进展，并对有关路由协议进行了评述，这些协议涵盖了目前能见到的绝大部分类型的MANET路由协议。     

Uncertainty analysis framework for trust based routing in MANET

MANET (Mobile Ad hoc Network) has distinctive characteristics like node mobility, broadcast nature of wireless communication, and peer to peer data transfer. Due to these characteristics uncertainty is an integral part of MANET behavior. Uncertainty quantification is important for performance evaluation and better decision making in MANET. Packet dropping is a serious issue in MANET which degrades the performance of the network to a great extent. The packet dropping attack increases uncertainty in the network communication and eventually of the MANET. Trust based routing mechanisms are useful for neutralizing packet dropping attack. There are many existing trust based routing protocols which uses uncertainty for precise trust calculations. Thus, trust and uncertainty are closely related to each other. The paper proposes Uncertainty Analysis Framework (UAF) for MANET, it calculates the network Belief, Disbelief, and Uncertainty (BDU) values. The UAF framework integrated into different trust variants of AODV protocol which use direct trust, indirect trust, and global trust. The research work discovers impact of different trust models on MANET BDU using various mobility models. Experimental analysis shows that, trust based routing protocols show average 3 % gain in packet delivery ratio and at least 5 % increase in the network belief.     

采用半贪心优化的节点非均匀分布路由协议

为避免无线传感器网络中因节点能耗不均衡而产生的能量空洞现象,延长网络生命周期,提出采用半贪心优化的节点非均匀分布路由协议。首先在网络监测区域分层的基础上,计算各层感知数据转发能耗,根据各层网络能耗比例和监测区域覆盖要求,设计了密度递减的节点部署模型;然后基于两跳通信的贪心范围,提出两跳能耗代价估计函数,改进半贪心算法;在簇间多跳通信阶段,利用优化的半贪心算法求解簇头到基站的最优转发路径。仿真实验表明,与现有的几种路由协议相比,新协议能够均衡各层网络节点能耗,延长网络生命周期,有效避免能量空洞现象。     

Scalability of MANET routing protocols for heterogeneous and homogenous networks

In Mobile Ad hoc Network (MANET), mobility, traffic and node density are main network conditions that significantly affect performance of routing protocols. Much of the previous research in MANET routing have focused on developing strategies, which suit one specific networking scenario. Therefore, there is no existing protocol that can work well in all different networking scenarios. This paper reviews characteristics of several different classes of routing protocols. Moreover, most of current routing protocols assume homogeneous networking conditions where all nodes have the same capabilities and resources. This paper presents extensive studies simulations for DSR, AODV, LAR1, FSR and WRP in homogenous and heterogeneous networks that consist of different nodes with different resources. The results showed that while all protocols perform reasonably well in homogenous networking conditions, their performance suffer significantly over heterogonous networks.     

一种基于改进RTS/CTS的MANET高效报文转发策略

MANET网络由可自主移动的无线节点组成。节点的自主移动导致了链路路由的改变,因此需要有一个机制维护和发现路由信息。目前人们已经针对MANET网络提出了几种路由协议,但这些路由协议都是基于IP的且路由维护的代价高,这严重影响了MANET网络的稳定性、可扩展性和用户有效带宽。本文提出了一种基于改进RTS/CTS的MANET高效报文转发策略。该策略对标准IEEE 802.11协议进行了修改,利用改进的RTS/CTS报文信息,进行报文转发,从而避免了使用MANET网络路由协议给网络性能带来的影响。使用改进的NS-2模拟了基于改进RTS/CTS的MANET高效报文转发策略。模拟结果表明:该策略可以有效地降低路由维护的开销并降低报文传输的延迟。     

航空自组网贪婪地理路由协议研究

在全面总结航空自组网路由协议研究现状的基础上,针对大尺度、高动态的航空通信环境,仿真评估了贪婪地理路由协议GPSR的适用性。仿真结果表明,当飞行器低速运动时,GPSR协议能够较好地适应航空自组网环境,性能优于AODV协议,然而当飞行器运动速率增大后,GPSR协议性能下降,难以满足高动态航空通信的需求,必须对协议中周期性HELLO发送机制、贪婪转发策略等方面进行改进。     

Standardisation advancements in the area of routing for mobile ad-hoc networks

Mobile Ad hoc Networks (MANETs) are self-organized and fully distributed networks that rely on the collaboration of participating devices to route data from source to destination. The MANET paradigm is expected to enable ubiquitous mobile communication and thus the proliferation of pervasive applications. The MANET Working Group (WG) of the Internet Engineering Task Force (IETF) is responsible for standardizing an appropriate Internet Protocol (IP) based routing protocol functionality for both static (mesh) and dynamic (mobile) wireless ad hoc network topologies. In this paper, we provide a background on the possibility to use MANETs for enabling future pervasive internet and innovative ubiquitous services. We also describe the work achieved by the MANET WG thus far on the area of secure unicast and multicast routing for MANETs. We also examine non-IETF work on this area, chiefly based on adaptive and hybrid routing. The paper then presents comparative performance evaluations of discussed routing protocols. It is mainly observed that there is a need for adaptive hybrid routing approaches in order to support future innovative and pervasive applications. Consequently, we present our conclusions.     

Survey of network coding-aware routing protocols in wireless networks

In recent times, there have been many advances in the field of information theory and wireless ad hoc network technologies. Regarding information theory progression and its connection with wireless ad hoc networks, this study presents fundamental concepts related to the application of the state-of-the-art Network Coding (NC) within wireless ad hoc networks in the context of routing. To begin with, this paper briefly describes opportunistic routing and identifies differentiation between NC-aware and NC-based routing mechanisms in wireless ad hoc networks. However, our main focus is to provide a survey of available NC-aware routing protocols that make forwarding decisions based on the information of available coding opportunities across several routes within wireless ad hoc networks. The taxonomy and characteristics of various representative NC-aware routing protocols will also be discussed. In summary, we provide a comparison of available NC-aware routing schemes and conclude that NC-aware routing techniques have several advantages over traditional routing in terms of high throughput, high reliability, and lower delay in a wireless scenario. To the best of our knowledge, this work is the first that provides comprehensive discussion about NC-aware routing protocols.     

采用Hull树的贪婪地理位置路由算法的设计

地理位置路由算法是指借助节点获得的地理位置信息进行无线传感网络中的路由发现与数据转发工作。本文提出一种基于Hull树的贪婪地理位置路由算法——Greedy Hull Tree Geographic Routing(GHTGR)。通过图形学中凸包的概念,在网络初始阶段分布式地在各节点上建立Hull树以探查网络局部拓扑结构;同时在数据分组的路由转发阶段,通过Hull树内的搜索,寻找下一跳转发节点,完成数据分组的转发传输。通过仿真实验表明,与现有地理位置路由算法相比,该算法能够正确地寻找数据转发路径,有效地减少网络能耗,提高网络传输性能。     

无线传感器网络通信空洞分析

本文简述无线传感器网络近代发展的情况。详细介绍了以地理位置信息为基础的贪婪路由算法。分析了现有的贪婪算法存在的不足,着重讨论了贪婪路由算法中通信空洞现象各种不同的解决方法。基于以上分析对地理位置信息在无线传感器网络路由协议的发展提出看法。     

基于贪婪算法无线传感器网络中继节点布局的研究

为实现远距离的无线通信, 在网络中添加中继节点, 采用多跳路由传输数据。对于中继节点的布局问题, 依据线性结构使网络整体能量消耗最小的特征, 提出一种中继节点贪婪布局算法。该算法通过最近贪婪策略、中继节点通信容量、传感器节点数据转发跳数等约束方法限制中继节点的布局位置。理论分析和实验验证了该算法能够有效减少能量消耗, 延长网络寿命。     

基于以太网的MANET网络试验床

在移动自组织网络（MANET）的研究中,一般采用软件仿真和现场试验的方式对所设计的路由协议进行验证。软件仿真常用来对路由协议的原理和性能进行初步验证,现场试验则常用在开发过程中的测试和产品上线之前的最终验证。在MANET的路由协议开发过程中采用现场试验的方式进行测试其结果虽然准确可靠,但是试验成本较高、操作相对较为复杂,并且试验结果容易受到地理环境等外界因素的影响。针对上述情况,本文提出一种基于有线以太网构建MANET网络试验床的方法,并基于VxWorks实时操作系统,设计和实现一个接近于真实试验环境的MANET网络试验床。该试验床对标准的TCP/IP协议栈进行扩展,在网络层和数据链路层中间添加模拟无线链路层,从而在有线链路上模拟节点移动、无线信道通信等MANET网络特性。此外,试验床还可以通过管控平台配置不同测试场景,并可以实时采集网络协议栈的各层试验数据,从而方便网络研究人员进行测试和验证。该试验床克服了现场试验成本高、操作复杂等缺点,解决了现场试验过程中很难对问题场景进行重现的问题,明显减少了试验时间,提高了开发效率。