A Cross-Layer Approach to Mixed-Control Topology Management for MANETs - SEMINAR

 

1. INTRODUCTION

 

 

            Mobile networking is one of the most important technologies supporting pervasive computing. During the last decade, advances in both hardware and software techniques have resulted in mobile hosts and wireless networking common and miscellaneous. Generally there are two distinct approaches for enabling wireless mobile units to communicate with each other: 

 

1) Infrastructured. Wireless mobile networks have traditionally been based on the cellular concept and relied on good infrastructure support, in which mobile devices communicate with access points like base stations connected to the fixed network infrastructure. Typical examples of this kind of wireless networks are GSM, UMTS, WLL, WLAN, etc. 

2) Infrastructureless. As to infrastructureless approach, the mobile wireless network is commonly known as a mobile ad hoc network (MANET) . A MANET is a collection of wireless nodes that can dynamically form a network to exchange information without using any pre-existing fixed network infrastructure. This is a very important part of communication technology that supports truly pervasive computing, because in many contexts information exchange between mobile units cannot rely on any fixed network infrastructure, but on rapid configuration of a wireless connections on-the-fly. Wireless ad hoc networks themselves are an independent, wide area of research and applications, instead of being only just a complement of the cellular system. 
 
MANET Concept 

            A mobile ad hoc network is a collection of wireless nodes that can dynamically be set up anywhere and anytime without using any pre-existing network infrastructure. It is an autonomous system in which mobile hosts connected by wireless links are free to move randomly and often act as routers at the same time. The traffic types in ad hoc networks are quite different from those in an infrastructured wireless network , including: 

1. Peer-to-Peer. Communication between two nodes which are within one hop. Network traffic (Bps) is usually consistent
2. Remote-to-Remote. Communication between two nodes beyond a single hop but which  maintain a stable route between them. This may be the result of several nodes staying within communication range of each other in a single area or possibly moving as a group. The traffic is similar to standard network traffic.
3. Dynamic Traffic. This occurs when nodes are dynamic and moving around. Routes must be    reconstructed. This results in a poor connectivity and network activity in short bursts. 

 

MANET Features 

MANET has the following features: 

1. Autonomous terminal. In MANET, each mobile terminal is an autonomous node, which may function as both a host and a router. In other words, besides the basic processing ability as a host, the mobile nodes can also perform switching functions as a router. So usually endpoints and switches are indistinguishable in MANET.
2. Distributed operation. Since there is no background network for the central control of the network operations, the control and management of the network is distributed among the terminals. The nodes involved in a MANET should collaborate amongst themselves and each node acts as a relay as needed, to implement functions e.g. security and routing. 
3. Multihop routing. Basic types of ad hoc routing algorithms can be single-hop and multihop, based on different link layer attributes and routing protocols. Single-hop MANET is simpler than multihop in terms of structure and implementation, with the cost of lesser functionality and applicability. When delivering data packets from a source to its destination out of the direct wireless transmission range, the packets should be forwarded via one or more intermediate nodes. 


4. Dynamic network topology. Since the nodes are mobile, the network topology may change rapidly and unpredictably and the connectivity among the terminals may vary with time. MANET should adapt to the traffic and propagation conditions as well as the mobility patterns of the mobile network nodes. The mobile nodes in the network dynamically establish routing among themselves as they move about, forming their own network on the fly. Moreover, a user in the MANET may not only operate within the ad hoc network, but may require access to a public fixed network.. 
5. Fluctuating link capacity. The nature of high bit-error rates of wireless connection might be more profound in a MANET. One end-to-end path can be shared by several sessions. The channel over which the terminals communicate is subject to noise, fading, and interference, and has less bandwidth than a wired network. In some scenarios, the path between any pair of users can traverse multiple wireless links and the link themselves can be heterogeneous. 
6. Light-weight terminals. In most cases, the MANET nodes are mobile devices with less CPU processing capability, small memory size, and low power storage. Such devices need optimized algorithms and mechanisms that implement the computing and communicating functions. 

 

MANET Applications 

            With the increase of portable devices as well as progress in wireless communication, ad hoc networking is gaining importance with the increasing number of widespread applications. Ad hoc networking can be applied anywhere where there is little or no communication infrastructure or the existing infrastructure is expensive or inconvenient to use. Ad hoc networking allows the devices to maintain connections to the network as well as easily adding and removing devices to and from the network. The set of applications for MANETs is diverse, ranging from large-scale, mobile, highly dynamic networks, to small, static networks that are constrained by power sources. Besides the legacy applications that move from traditional infrastructured environment into the ad hoc context, a great deal of new services can and will be generated for the new environment. Typical applications include: 

1) Military battlefield. Military equipment now routinely contains some sort of computer equipment. Ad hoc networking would allow the military to take advantage of commonplace network technology to maintain an information network between the soldiers, vehicles, and military information head quarters. The basic techniques of ad hoc network came from this field. 

2) Commercial sector. Ad hoc can be used in emergency/rescue operations for disaster relief efforts, e.g. in fire, flood, or earthquake. Emergency rescue operations must take place where non-existing or damaged communications infrastructure and rapid deployment of a communication network is needed. Information is relayed from one rescue team member to another over a small handheld. Other commercial scenarios include e.g. ship-to-ship ad hoc mobile communication, law enforcement, etc. 

3) Local level. Ad hoc networks can autonomously link an instant and temporary multimedia network using notebook computers or palmtop computers to spread and share information among participants at a e.g. conference or classroom. Another appropriate local level application might be in home networks where devices can communicate directly to exchange information. Similarly in other civilian environments like taxicab, sports stadium, boat and small aircraft, mobile ad hoc communications will have many aplications. 

4) Personal Area Network (PAN). Short-range MANET can simplify the intercommunication between various mobile devices (such as a PDA, a laptop, and a cellular phone). Tedious wired cables are replaced with wireless connections. Such an ad hoc network can also extend the access to the Internet or other networks by mechanisms e.g. Wireless LAN (WLAN), GPRS, and UMTS. The PAN is potentially a promising application field of MANET in the future pervasive computing context. 
 
  

MANET Challenges 

            Regardless of the attractive applications, the features of MANET introduce several challenges that must be studied  carefully before a wide commercial deployment can be expected. These include: 

1) Routing. Since the topology of the network is constantly changing, the issue of routing packets between any pair of nodes becomes a challenging task. Most protocols should be based on reactive routing instead of proactive. Multicast routing is another challenge because the multicast tree is no longer static due to the random movement of nodes within the network. Routes between nodes may potentially contain multiple hops, which is more complex than the single hop communication. 

2) Security and Reliability. In addition to the common vulnerabilities of wireless connection, an ad hoc network has its particular security problems due to e.g. nasty neighbour relaying packets. The feature of distributed operation requires different schemes of authentication and key management. Further, wireless link characteristics introduce also reliability problems, because of the limited wireless transmission range, the broadcast nature of the wireless medium (e.g. hidden terminal problem), mobility-induced packet losses, and data transmission errors. 

3) Quality of Service (QoS). Providing different quality of service levels in a constantly changing environment will be a challenge. The inherent stochastic feature of communications quality in a MANET makes it difficult to offer fixed guarantees on the services offered to a device. An adaptive QoS must be implemented over the traditional resource reservation to support the multimedia services. 

4) Internetworking. In addition to the communication within an ad hoc network, internetworking between MANET and fixed networks (mainly IP based) is often expected in many cases. The coexistence of routing protocols in such a mobile device is a challenge for the harmonious mobility management. 

5) Power Consumption. For most of the light-weight mobile terminals, the communication-related functions should be optimised for lean power consumption. Conservation of power and power-aware routing must be taken into consideration. 
 

2. LITERATURE SURVEY

Optimal transmission ranges for randomly distributed packet radio terminals 

H. Takagi and L. Keinrock

 

            ONE of the key issues in providing’ efficient and costeffective multihop packet radio networks is to find an adequate transmission power for each terminal in the network. The environment we have in mind is one in which communicating terminals are geographically distributed and possibly mobile and require multiaccess to a communication channel shared among themselves. It has been shown  that the spatial reuse of the channel obtained by reducing the transmission power to such a level that only a few neighbors are within the range gives rise to an improved throughput for the network. However, since the purpose of transmitting packets in a multihop environment is to advance them towards their destinations, a more appropriate measure of performance is the expected one-hop progress of a packet in the desired direction. 

 

            The optimal transmission power to maximize the expected progress involves the following tradeoff. A short-range transmission is favorable in terms of successful transmission because of its low possibility of collision  at the receiver. A long-range transmission is favorable because l) it moves a packet far ahead in one hop if successful, and 2) there is high probability of finding a candidate receiver in the desired direction. Roughly speaking, if we denote by N the average nurnbe,r of terminals within the transmission radius , then the probability of successful transmission is proportional to 1/N, whereas the progress is proportional to a,a nd the contribution from the receiver’s angular position is expressed as a monotonically increasing function of N from 0 to some asymptotic value. Thus, we see that there must exist an optimal value of N, which maximizes the obtainable expected progress. 

This paper elaborates on these ideas with a variety of transmission protocols and network configurations. The protocols considered here include slotted ALOHA  and nonpersistent carrier-sense-multipleaccess.

            Terminals are randomly located in the plane according to a two-dimensional Poisson distribution with homogeneous or inhomogeneous density. Each section below begins with the description of the model used in that section, followed by the formulation of the optimization problem. The optimal transmission range is found, and the performance is compared to other models.  

An interference-aware and power efficient topology control algorithm for wireless multi-hop networks

H. Chuanhe, C. Yong, L. Yuan, S. Wenming, and Z. Hao:

            This paper investigates topology control and seeks to find a distributed solution with low interference, high performance. 

 

            Multi-hop wireless networks, such as radio networks , ad hoc networks , and sensor networks , are networks where communication between two nodes may go through multiple consecutive wireless links without relying on any existing, pre-configured network infrastructure or centralized control. These networks are constrained by the interference of wireless communications, the finite battery energy and the mobility of nodes. To address these issues, the primary goal of topology control is to design power efficient algorithms that reduce energy consumption, reduce interference, and increase effective network capacity, while maintaining connectivity. The primary method of accomplishing topology control is to adjust

the transmission power of the mobile nodes. To simplify deployment and reconfiguration in the presence of failures and mobility, distributed topology control algorithms that utilize only local information and allow asynchronous operations are particularly attractive. 

            Our goal for topology control is to find an undirected sub-graph G of GR such that (1) G consists of all the nodes in GR but has fewer edges. (2) if u and v are connected in GR, they are still connected in G. (3) For any two nodes u and v, if the optimal path between u and v in GR has cost c, then the optimal path between u and v in G has cost f(c) (If f(c) is bounded from above by a linear function in c, the graph G is called a spanner). (4)

            The remaining graph G should be sparse, that is, the number of links should be in the order of the number of nodes, i.e. |G| = O(|V|). (5) A node can transmit to all its neighbors in G consuming less power than is required to transmit to all its neighbors in GR. Since minimum power consumption is so important, it is desirable to find a graph satisfying these properties to minimize the amount of power that a node needs to consume to communicate with all its neighbors. 

 

This paper proposes a distributed topology control algorithm called CBDTG (Cone Based Delaunay Triangulation Generation Algorithm) by using the method of adjusting transmission power and the computational geometry, which is based on the CBTC (Cone-Based Distributed Topology-Control Algorithm). 

Distributed topology control in multichannel multi-radio mesh networks 

H. Zhu, K. Lu, and M. Li:

 

            In this paper, we propose a Distributed Topology Control (DTC) and the associated inter-layer interfacing architecture for efficient channel-interface resource allocation in multi-channel multi-radio (MCMR) mesh networks. The proposed solution is (i) routing agnostic but traffic adaptive; (ii) it fully achieves channel multiplexing over multiple interfaces; (iii) its well-defined over-the-air signaling mechanism can be incorporated with various distributed topology optimization algorithms; and (iv) it is fairly PHY/MAC-agnostic and can be integrated with various mesh access technologies. 

 

            Multi-channel multi-radio (MCMR) solution has attracted a lot of attention recently because it has the potential to solve the scalability problem of wireless mesh networks. Low cost radio design has made such solution economically feasible. However, it also places challenges in various new issues. Due to the space limit, we will not elaborate more on other related issues, such as multi-channel MAC design  and focus on one major challenge, which is how to dynamically allocate both radio interface and channel resource to achieve efficient spatial and spectrum reuse.  

            We investigate distributed topology control for efficient channel-interface resource utilization in MCMR networks. Simulation results show significant performance gains on network capacity by adopting the proposed DTC. In future work, we plan to further investigate other decision policies, under the same over-the-air signaling handshaking framework. 

A survey on topology control in wireless sensor networks 

Z. Gengzhong and L. Qiumei,

 

            Wireless sensor networks have a wide range of potential, practical and useful applications. However, there are many challenging problems that need to be addressed for efficient operation of wireless sensor networks in real applications. One of the fundamental and important problems in sensor networks is the topology control problem since most sensors are equipped with non-rechargeable batteries and the density of deployed sensors is very high. Topology control needs to reduce the power-consumption and extend the lifetime of sensor networks while satisfying certain application requirements. To energy-efficient control the topology structure of sensor networks, the common approaches are to adjust the transmission power of sensors and to dynamically schedule sensor’s cycles. In this paper, we survey the state-of-the art topology control techniques, present an overview and analysis of the solutions proposed in recent research literature. 

 

            First, topology control is the primary technique of energy saving, and energy saving is also one of the most important objectives in topology control. Second, topology control should ensure the quality of network coverage and connectivity. Coverage and connectivity are the precondition for effective monitor and data collection in wireless sensor networks. Third, topology control can reduce the signal interference of radio and improve the efficiency of MAC and routing protocols. At last, topology control can increase the network performance, such as robustness, reliability, and scalability. 

            This paper analyses the technologies and difficulties involved in design the topology control algorithms, summarizes current work and relevant evolution, and the challenges. The rest of the paper is organized as follows. Section 2 discusses the network model while designing the different topology control algorithms. Section 3 describes the design objectives. 

  
  3. PROBLEM STATEMENT

 

 

            Due to the differences in capabilities of each platform, the follower is responsible for maintaining a critical control link to the leader platforms. While remote operators are free to navigate the leaders, the follower node is responsible for maintaining the control channel within strict levels of service and reliability. The connectivity link between the UAVs is affected by the distance between the platforms and the relative banking, so the main task of the follower platform is to ensure a minimum level of QoS requirement between the two platforms so the communication channel provided to the leader can be properly maintained at all times. While engaged with the target, the leader node receives a continuous command stream through the follower, and periodically reports to the follower a short term average SINR of the control channel. The follower node, operating as a relay, closely monitors the quality of the control channel and continuously adjusts its relative distance from the leader to maintain the required level of service. However, for a given constant transmit power level, it is likely that delays in response due to the dynamics of each platform will lead to significant variations on SINR. 

 

            Alternatively, a combined control strategy could leverage the best capabilities of each control variable, relying on power management to compensate for high frequency variations of SINR and mobility control to compensate for the long term trends in SINR variation.  

 
 

4. PROPOSED METHODOLOGY

 

4.1 Topology control algorithm 

            Topology control algorithm combines information from the communications stack and the mobility of the platform. The control algorithms for mobility and power management have SINR as their objective function and independently adjust their control metrics (distance and power) to stabilize the system around a desired SINR. By tuning the control variables (k1 and k2), the response of the power control can be balanced with the mobility response.

 

            While effective as a control strategy, the  proposed design tends to keep the system operating at maximum power. Upon an immediate power adjustment, if the system reaches a point of desired SINR, there is no need for node mobility. 

 

4.2 Greedy algorithm

            A greedy algorithm that achieves an O(log n) approximation ratio, the same guarantee that can be achieved by the greedy algorithms. The solution differs in the sense that it is directly formulated and analyzed in the interference model. Many of the algorithmic challenges faced in designing approximation algorithms for interference problems stem from the fact that an edge in the resulting graph exists only if both nodes set their transmission range to a sufficiently large value. This leads to situations in which an edge (a1; a2) may be cheap (interference-wise) at node a1, but costly at node a2. Another peculiar aspect is that establishing an edge between two nodes (a1; a2) may potentially be free of charge if both nodes have an edge that requires higher transmission range . Similarly, setting up an edge can be free of charge at one node, but expensive at the other. The combination of these characteristics render interference problems difficult to tackle in practice and appealing for theoretical study. 

 

5. CONCLUSION

 

 

            Topology management in tactical networks can be achieved through multiple control mechanisms at different levels in the communications stack. In this paper we have introduced a mixed topology control algorithm that combines two control inputs (transmit power and node mobility) operating at different time scales. The concept is generally extensible to other control strategies and suggests that, if properly coordinated, mixed control strategies can accommodate both the transient and the steady state requirements of the system. We tested our proof-of concept implementation against simple simulated environments, showing encouraging results. While our studies are still preliminary at this point, we are confident that mixed control strategies can play an important role on protocols for topology management and control. 

 

            Our future work includes the implementation of the proposed strategy as a control module for XLayer, as well as the evaluation of the control algorithms under emulated and realistic timing requirements using MLAB , a hybrid emulation testbed developed in collaboration with the U.S. Air Force Research Laboratory that enables the use of theoretical and data-driven link emulation models for airborne networks. 
 
 

REFERENCES

[1]        H. Takagi and L. Keinrock  :Optimal transmission ranges for randomly distributed packet radio terminals. 

[2]        T. Moscibroda and R. Wattenhofer :Minimizing interference in ad hoc and sensor networks in DIALM-POMC ’05: Proceedings of the 2005 joint workshop on Foundations of mobile computing. New York, NY, USA: ACM, 2005, pp. 24–33. 

[3]        H. Chuanhe, C. Yong, L. Yuan, S. Wenming, and Z. Hao :An interference-aware and power efficient topology control algorithm for wireless multi-hop networks in PERCOM ’08: Proceedings of the 2008 Sixth Annual IEEE International Conference on Pervasive Computing and Communications. Washington, DC, USA. 

[4]        H. Zhu, K. Lu, and M. L i:Distributed topology control in multichannel multi-radio mesh networks ICC 2008, May 19, 2008 - May 23, 2008. ArgonST/San Diego Research Center, San Diego, CA 92121, United States: Institute of Electrical and Electronics Engineers Inc., 2008, pp. 2958–2962. 

[5]        Z. Gengzhong and L. Qiumei :A survey on topology control in wireless sensor networks in ICFN ’10: Proceedings of the 2010 Second International Conference on Future Networks. Washington, DC, USA. 

[6]        T. Zhang, K. Yang, and H.-H. Chen :Topology control for serviceoriented wireless mesh networks Wireless Commun., vol. 16, no. 4, pp. 64–71, 2009. 

[7]        M. Carvalho, A. Granados, W. Naqvi, A. Brothers, J. P. Hanna, and K. Turck :A cross-layer communications substrate for tactical information management systems in Military Communications Conference (MILCOM) Nov. 2008. 

[8]        M. Cardei, J. Wu, and S. Yang :Topology control in ad hoc wireless networks using cooperative communication. 

[9]        T. Moscibroda and R. Wattenhofer: Minimizing interference in ad hoc and sensor networks in DIALM-POMC : Proceedings of the joint workshop on Foundations of mobile computing. New York, NY, USA. 

[10]      M. Carvalho, A. Granados, R. Carff, M. Arguedas, C. Perez, and D. Edwards :MLAB: A hybrid emulation testbed Institute for Human and Machine Cognition, Tech. Rep., January 2010.