Evolutionary Algorithms for Mobile Ad Hoc Networks

Bernabé Dorronsoro, Patricia Ruiz, Grégoire Danoy, Yoann Pigné, Pascal Bouvry

• Publisher: Wiley
• Year: 2014
• Print ISBN: 9781118341131
• eBook ISBN: 9781118832028
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming Algorithms
• Index: Computer Science

Describes how evolutionary algorithms (EAs) can be used to identify, model, and minimize day-to-day problems that arise for researchers in optimization and mobile networking

Mobile ad hoc networks (MANETs), vehicular networks (VANETs), sensor networks (SNs), and hybrid networks—each of these require a designer's keen sense and knowledge of evolutionary algorithms in order to help with the common issues that plague professionals involved in optimization and mobile networking.

This book introduces readers to both mobile ad hoc networks and evolutionary algorithms, presenting basic concepts as well as detailed descriptions of each. It demonstrates how metaheuristics and evolutionary algorithms (EAs) can be used to help provide low-cost operations in the optimization process—allowing designers to put some "intelligence" or sophistication into the design. It also offers efficient and accurate information on dissemination algorithms, topology management, and mobility models to address challenges in the field.

Evolutionary Algorithms for Mobile Ad Hoc Networks:

• Instructs on how to identify, model, and optimize solutions to problems that arise in daily research
• Presents complete and up-to-date surveys on topics like network and mobility simulators
• Provides sample problems along with solutions/descriptions used to solve each, with performance comparisons
• Covers current, relevant issues in mobile networks, like energy use, broadcasting performance, device mobility, and more

Evolutionary Algorithms for Mobile Ad Hoc Networks is an ideal book for researchers and students involved in mobile networks, optimization, advanced search techniques, and multi-objective optimization.

PART I
BASIC CONCEPTS AND LITERATURE REVIEW

1
INTRODUCTION TO MOBILE AD HOC NETWORKS

The first wireless communication network between computers was created in 1970 by Norman Abramson at the University of Hawaii, the AlohaNet [11]. It was composed of seven computers distributed over four islands that were able to communicate with a central node on Oahu using radio communication. Additionally, the most well-known random-access protocol, ALOHA, was also developed and presented at that time [12]. The ALOHA channel is used nowadays in all major mobile networks (2G and 3G), as well as in almost all two-way satellite data networks [58].

Thanks to the reduction in the cost and size of the hardware needed, the wireless technology widely extends in our everyday life. The huge number of devices that provide wireless technology nowadays, as well as the increasing number of people that not only carry a device with wireless capabilities but actually use it, make the field of wireless technology a key topic in research.

The current mobile wireless networks consist of wireless nodes that are connected to a central base station. When a device moves to a different geographical area, it must connect to a different base station in order to continue with the service. This means that two nodes located in the same region cannot communicate unless there is a base station associated to that area. Researchers envisioned a possibility for communicating devices where the fixed infrastructure was not available, that is, remote or disaster areas. This kind of network is called an ad hoc network.

The term ad hoc has been extensively used during the last decade. Accord-ingtothe American Heritage Dictionary of the English Language,ithas two different meanings: (1) form for or concerned with one specific purpose and (2) improvised and often impromptu. These two definitions of the term ad hoc describe the purpose of a new kind of network that emerged with the wireless technology.

Definition 1 Ad hoc Network. It is a decentralized and self-configuring network spontaneously created between neighboring devices with communication capabilities, without relying on any existing infrastructure.

In an ad hoc network, all devices may also act as routers and forward packets to enable communication between nodes that are not in range. Two nodes are said to be in range when they are able to receive and properly decode packets sent by the other node.

Some examples where the deployment of an ad hoc network can be used and actually can be very useful are relief in disaster areas, battlefield deployment, sensing areas, social events (like a concert), and the like. In those cases, devices can create a temporary network for a specific purpose, that is, an ad hoc network. When devices are mobile, they are called mobile ad hoc networks.

Ad hoc networks suffer from the typical drawbacks of wireless networks such as interference, time-varying channels, low reliability, limited transmission range, and so forth. Additionally, ad hoc networks have specific characteristics that make their deployment very challenging. Next, we describe the main ones:

1. Decentralization: nodes locally execute the algorithms and take all decisions by themselves:
2. Self-organization: nodes must be able to create, join, and manage an ad hoc network by their own means.
3. Limited network resources: the medium is shared between all devices in range.
4. Energy limitations: devices rely on battery.
5. Dynamism: nodes move, appear and disappear from the network.
6. Heterogeneity: any kind of device with wireless capabilities may be able to join the network.
7. Scalability: nodes can join or leave the network at any time, therefore the number of nodes composing it is unpredictable.
8. Multihop: in order to communicate two remote nodes, devices have to also act as routers forwarding packets not intended for themselves.
9. Security: the lack of central authority, the changing topology, and the vulnerability of the channel makes difficult guaranteeing secure communications.

Chlamtac et al. [20] presented a classification of ad hoc networks in terms of the coverage of the devices (see Fig. 1.1). They can be differentiated into five different classes, explained below.

Figure 1.1. Classification of ad hoc networks in terms of the coverage area.

• Body area network (BAN) is a communication network (usually wireless) composed of small wearable nodes (earphones, microphones) that provides connectivity between those devices. It is also extended to small sensor nodes implanted in the human body that collect information about the patient's health and send it to an external unit. The range needed is just to cover the human body (i.e., 1−2 m).
• Personal area network (PAN) enables the communication of mobile devices carried by individuals, like smart phones, PDAs, and the like to other devices. The range varies with the technology used, from 10 to 100 m.
• Local area network (LAN) interconnects computer nodes with peripheral equipment at high data transfer in a predefined area such as an office, school, or laboratory. The communication range is restricted to a building or a set of buildings, between 100 and 500 m.
• Metropolitan area network (MAN) spans a city or a large campus. It usually interconnects different LANs. The size is variable, covering up to tens of kilometers.
• Wide area network (WAN) covers a large geographical area. It can relay data between different LANs or over long distances.

Both MAN and WAN still need much more work to become a reality in a near future. There are many challenges that are not solved yet like communication beyond line of sight, identification of devices, routing algorithms, and the like that keep researchers working on the topic [35, 38, 39, 68].

Apart from this classification, the ad hoc networking field has three well-defined research lines: (1) mobile ad hoc networks, (2) vehicular ad hoc networks, and (3) sensor networks. The first one is defined as an ad hoc network where devices do move and includes all personal devices like smart phones, PDAs, laptops, and gaming devices. When devices move at high speeds, without energy restrictions and the network is able to use road side units for communicating, we are talking about vehicular ad hoc networks. Finally, in sensor networks devices are generally meant to acquire data from the environment and report it to a central node or gateway. The next sections give a more detailed view of these three types of ad hoc networks.

1.1 MOBILE AD HOC NETWORKS

Mobile ad hoc networks, also called MANETs, are ad hoc networks where the devices that make up the network are mobile. Khan [43] extended the previously mentioned AlohaNet including repeaters, authentication, and coexistence with other possible systems in the same band. This new system was called the packet radio network, PRNET [43]. The PRNET project of the Defense Advanced Research Projects Agency, DARPA, started in 1973 and evolved through the years (1973-1987) to be a robust, reliable, operational experimental network. The MANETs were first defined in PRNET project. In Jubin and Tornow [41], a detailed description of PRNET is presented and in [40] PRNET is defined as a mobile ad hoc network.

Initially, MANETs were mainly developed for military applications, specially for creating communication networks on the battlefield. In the middle of 1991, when the first standard was defined (IEEE 802.11 [69]), and the first commercial radio technologies appeared, the great potential of ad hoc networks outside the military domain was envisioned. Apart from the military scenarios, all the previously mentioned applications for ad hoc networks (if we consider moving devices) are considered in this section. However, there are many applications like emergency services, multiuser gaming, e-commerce, information services, mobile office, that extend the cellular network.

Advances in the technology made possible Internet connection in portable devices. Mobile phones evolved to smart phones with large screens, cameras, GPS, bluetooth, high-speed da...

Table of contents

• COVER
• SERIES PAGE
• TITLE PAGE
• COPYRIGHT PAGE
• DEDICATION
• PREFACE
• PART I: BASIC CONCEPTS AND LITERATURE REVIEW
• PART II: PROBLEMS OPTIMIZATION
• INDEX
• END USER LICENSE AGREEMENT