The Research On Routing Algorithm In Wireless Ad Hoc Network

With the rapid development of Internet, the network technology changes frequently. Wired network can not satisfy the people's requirement for establishing communication, anytime and anywhere, which promotes the development of wireless network technology. Wireless ad hoc network is a particularly challenging class of wireless network. It is a network formed without any infrastructure which consists of nodes that use a wireless interface to deliver packet data, and the nodes in a network of this kind can serve as routers and hosts. Different from other kinds of wireless networks, ad hoc network has some characteristics, such as not relying on fixed infrastructure for communication, self-organization, self-management and so on. The routing algorithm is the fundamental and most important issue for the wireless communications in ad hoc network. However, compared with traditional networks, the development of routing algorithm in ad hoc network is more challenging, which has received considerable attention. There are some preliminary research results about routing in ad hoc netoworks, but there is no perfect solution. Thus, there is a vast space for further study in ad hoc networks. Nodes in an ad hoc network can be not only static but also mobile. Recently, the typical classes of ad hoc networks are the wireless sensor network (WSN) with static nodes and the vehicular ad hoc network (VANET), which have attracted great interest in the research community.Based on a systematical summary of relevant works on wireless sensor networks and vehicular ad hoc networks, this dissertation focuses on related technologies of the routing algorithms affected by the energy hole problem in WSN and characters in VANET such as rapidly changing topology, and gains several achievements on some sub-topics. The major contributions of this dissertation are as belows:1. In this paper we propose an improved corona model with levels for analyzing sensors with adjustable transmission ranges in a WSN with circular multi-hop deployment (modeled as concentric coronas). Based on the corona model, we divide the maximal transmission range of sensors into several levels. Nodes in the same corona have the same transmission range level termed the transmission range of the corona, and different coronas have different transmission ranges, which compose a list termed transmission range list. We conclude that the transmission ranges assignment of all coronas is the most effectively approach to prolong the network lifetime after nodes deployment. We prove that searching optimal transmission range list among all coronas is a multi-objective optimization problem (MOP), which is NP hard.2. We propose three algorithms to obtain approximate optimal transmission range lists for different node distributions. CETT (Centralized algorithm for energy-efficient transmission trees) is an algorithm of searching approximate optimal transmission range lists with maximal network lifetime from inner corona to outmost step by step. In uniform node distribution, before nodes deployment we can obtain the transmission range list by CETT based on the information about deployment, such as radius of the whole area, density and so on. After deployment, nodes in each corona transmit data according to the transmission range list. In non-uniform node distribution, we need DETL (Distributed algorithm for energy-efficient transmission range list) to optimize the list derived from CETT after nodes deployment. In DETL, in order to balance the energy consumption of all coronas, each corona adaptively adjusts its strategy of sending and receiving data. In all simulations, we can see the network lifetime is significantly extended when the two algorithms are adopted, and they can not only reduce the searching complexity but also obtain results approximated to the optimal solution. We also propose an ACO-based distributed algorithm (AASTRL) to prolong the network lifetime, which can help nodes in different areas to adaptively find approximate optimal transmission range based on the node distribution. This alogorithm can be used not only in uniform node distribution but also in non-uniform node distribution. Furthermore, the simulation results indicate that the network lifetime under our solution approximates to that using the optimal list. Compared with existing algorithms, our ACO-based algorithm can make the network lifetime be significantly extended.3. We analyze the routing problem in VANET, and classify recent routing protocols in VANET into three categories. We propose a Macro-Micro Model from both macroscopic and microscopic aiming at effectively analyzing and designing routing strategies in VANETs. In Macro-Micro Model, we assume Macro has stable state for creating routes and Micro is responsible for packet delivery along each road. 4. In order to exactly estimate network delay and avoid network congestion, we propose the Distributed Real-time Delay Estimation (DRDE) in Macro for evaluating the packet delivery delay along each road. Considering the effectiveness of estimation and the cost of storage space, we combine weighted average with recursive method to evaluate the delay of each road. We propose the delay estimation assisted greedy forwarding protocol (DEAGF) in Micro for guaranteeing a correct delivery of each packet. In order to increase the probability of delivering messages to the right road at each intersection, we propose road aware epidemic routing protocol (RAEP) with the way of TTL (time-to-live), which can not only increase the efficiency of data delivery along routing path (especially at intersections) but also reduce the consumption of resource.