Memetic and Evolutionary Design of Wireless Sensor Networks Based on Complex Network Characteristics

Memetic and Evolutionary Design of Wireless Sensor Networks Based on Complex Network Characteristics

André Siqueira Ruela, Raquel da Silva Cabral, André Luiz Lins Aquino, Frederico Gadelha Guimarães
Copyright: © 2010 |Pages: 21
DOI: 10.4018/jncr.2010040103
(Individual Articles)
No Current Special Offers


This work proposes the design of wireless sensor networks using evolutionary algorithms based on complex network measures. In this paper, the authors develop heuristic approaches based on genetic and memetic algorithms for finding a network configuration based on two complex network measures, the average shortest path length, and the cluster coefficient. The work begins with the mathematical model of the hub allocation problem, developed to determine the nodes that will be configured as hubs. This model was adopted within the basic and the hybrid genetic algorithm, and results reveal that the methodology allows the configuration of networks with more than a hundred nodes where some complex network measures are observed in the physical communication layer. The energy consumption and the delay could be reduced when a tree based routing is built over this physical layer.
Article Preview

I. Introduction

Wireless Sensor Networks (WSNs) (Akyildiz, Su, Sankarasubramaniam, & Cayirci, 2002) represent an emerging technology that allows the monitoring and control of physical and environmental variables and conditions, such as temperature, sound, light, vibration, pressure, movement, and pollution. A WSN consists of a great number of wireless autonomous devices, called sensor nodes, which work in a cooperative way to perform many different functions. These characteristics make the WSNs a promising technology in a wide range of application domains, for instance, biotechnology, industry, public health, and transportation.

WSNs differ in many aspects from conventional computer networks, mainly because a WSN has several resource restrictions, such as low computational power, reduced bandwidth, and limited energy source. Due to these characteristics, it is necessary to design specific models, topologies and algorithms to circumvent the difficulties related to this technology (Li, Thai, & Wu, 2008; Sohraby, Minoli, & Znati, 2007). Among these resource restrictions, energy consumption is critical in WSNs. The operation of wireless data communication is the main source of energy consumption: sending one bit demands on average thousand times more energy than other internal operations and data sensing. Therefore, algorithms for WSNs need to be carefully designed. Sending a large amount of data can be problematic, causing excessive delay in response time, thus invalidating the data. Moreover, a large traffic on the network can diminish its lifetime. Due to these restrictions, in some cases, it is necessary to adopt specific infrastructure designs to balance network requirements while keeping its functionality.

WSNs are classified as Mobile Ad Hoc Networks (MANET), since there is no intermediate base station providing some infrastructure to the network, as in cellular networks. However, WSNs present some characteristics that make them more specific than MANETs, such as the number of elements in the network and the density of data, with high unidirectional data flow.

Generally, the information about the phenomenon being monitored is converted in digital data by the sensor nodes, termed as source nodes, and reported through the network to the sink node, which is a special node in the network that gathers all the data reported. The quality of service of a WSN is directly related to its life time, which in turn depends on the capacity and energy consumption of its elements. As remarked before, data transmission is the most expensive operation in the network. Therefore, considering the whole network, the data propagation from all nodes to the sink is directly related to the life time of the network.

Data propagation to the sink is performed considering a specific routing strategy. Examples of routing strategies are depicted in Figures 1–3. A simple naive, but inefficient, way of propagating information through the network is flooding, see Figure 1. In this case, the information is flooded to all sensors until it reaches the sink node (Maroti, 2004). This strategy causes unnecessary communication, consequently, large energy consumption, high response time to deliver the data, and redundant data.

Figure 1.

Flooding propagation

Figure 3.

Routing tree propagation over a complex network physical layer


A common alternative to flooding is tree routing, see Figure 2, a simple and low overhead routing protocol. Using a tree routing, each sensor is configured to send its data only to a specific sensor node, denoted father node. The choice of which node will be the father depends on the policy established by the application, in general, the shortest path policy is used (Qiu, Skafidas, & Hao, 2009). The major drawbacks of using the tree routing strategy are the increased number of hop counts as compared with more sophisticated path search protocols and the low reliability, since the failure of a given node can disconnect the network. This situation can be seen in Figure 2.

Complete Article List

Search this Journal:
Volume 12: 1 Issue (2024): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2021)
Volume 9: 4 Issues (2020)
Volume 8: 4 Issues (2019)
Volume 7: 4 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing