EMR – Energy-efficient Multi-hop Routing for Clustered WS&ANs Cookbook

This document aims to introduce about how to use the resource of Energy-efficient Multi-hop Routing (EMR) for Clustered WSNs, e.g. how to install the codes of routing solution and how to run it. It first gives some background about EMR, for instance the main issue it aims to addres, its objective and its operation. Then the required devices and soft wear environment to install EMR resource are described. After illustrating how to install the EMR resource, it briefly explains how to run this routing solution.

Table of Contents

  1. Introduction
    1. Hot-spot issue in WSNs
    2. Objectives of EMR
    3. Operation of EMR
  2. Installation
    1. Hardware and Software Requirements
    2. Installation
  3. Running EMR
  4. Demonstration
    1. Device deployment and demonstration tool
    2. The expectation of demonstration


Hot-spot issue in WSNs

In a typical WSN, raw data packets from sensor nodes are typically sent to sink for further process, resutling in that nodes in the network may have different loads. In a WSN where data packets are relayed to the sink via multi-hop routing (typically in large-scale WSNs), those nodes nearer the sink may required to relay more data and thus will have higher load; whereas in a WSN where data packets are forwarded to the sink directly (typically in small-scale WSNs), those nodes that are farther away from the sink require higher power to access the sink and thus will have higher load. Such phenomenon that senor nodes have different loads in the network and drain energy at an uneven rate is referred to as hot-spot issue. In a WSN with uniform inital energy distribution, hot-spot issue may differ node lifetime, i.e. those nodes with higher load will deplete energy earliers than others.

Though the hot-spot issue may differ the node lifetime in a network, the connectivity between the WSN island and the sink may be still existing after some nodes have depleted energy. In a WSN with multi-hop routing towards the sink, in case the nodes deployed in the area next to the sink have depleted energy, the nodes in the neighboring areas, e.g. with longer distance to the sink, could increase the power for routing discovery and could probably still be able to access the sink. In a WSN with single-hop between the sensor nodes and the sink, those nodes with longer distance to the sink are more likely to die, yet their earlier death will not bring any effect to the snesor nodes nearer the sinks in this case. To summarize, the death of some nodes in the network due to energy depletion may not disconnect the island and the sink. This means that a user is still able to enquire the information of the network after some network nodes died due to energy failure. However, in case the users enquire the area where the deployed sensor nodes have depleted energy, the SENSEI system may fail to provide the quality informaiton. From this point of view, hot-spot issue will degrade the performance of the SENSEI framework and thus needs to be addressed.

Objectives of EMR

The EMR solution is proposed for such purpose to address the hot-spot issue. It mainly aims to extend the stable operation period (SOP) of the network during which all sensor nodes are alive with avaialbe energy. The SOP is important for a WSN as during the SOP period, the whole island is supposed to be covered by the active sensor nodes i.e. with avaialbe energy (assuming that the deployed sensor nodes are able to cover the entire network) and the SENSEI system is able to provide the quality infroamtion to the user. Therefore, extending SOP means longer continuity of the SENSEI system duirng which the system could provide quality informaiton.

The proposed EMR includes two main parts, the first is to conduct the mathematical analysis to theoriotically address the hot-spot issue. With the analysis, the competetion range to be a clusterhead (CH) is output. These rangea are then applied in EMR for CH selection.

Operation of EMR

The operation of EMR is separated into rounds of data collection. During each round, the following operations happen.

  • First of all, some CH candidates are selected among the nodes.
  • Then, these candidates announce their willing to be the CH and compete to be a final CH. Typically, those candidates with more avaialbe enregy will be a fianl CH.
  • After the CHs are selected, they announce their role and allow non-CH nodes to join them as member nodes to form the clusters.
  • Then each CH gives a slot to each member node in its cluster and collects the data packets from its respective member nodes;
  • Finally, each CH aggregates these packets from the member nodes as one summary packet of its cluster and delivers this summary packet to the sink.


Hardware and Software Requirements

Installing the EMR protocol requires the following hardware tools and software packages:

We assume that the installation PC is running a Linux operating system, and the TinyOS-2.x and JAVA environment have been installed and configured properly. We skip the installation of TinyOS. A user could refer to TinyOS-2.x about the installation if necessary. Please note that the description about how to install the EMR routing solution is based on the Ubuntu operating system.

EMR assumes that there are two types of nodes in a WSN, the normal nodes (please note that a normal node in EMR could be either a member node or a CH) and the sink. The software packages for normal nodes and the sink are separated. The following provides the detailed information about the structure and the content of the EMR software package:

  • For a normal node
      Contains the configuration files and the wiring between interfaces
      Contains all relevant actions and behavior of the CH, e.g. collecting the informaiton of the member nodes like how many member nodes belong it, receiving the data packets from the member nodes, and forwarding the summary packet of the cluster towards the sink
      Contains the procedure about how the clusters are formed
      Contains all initializations of each round across the network operation, and how to process the received message
      Contains general functionalities that could be used by other modules, e.g. the energy consumption model
      Contains all recelvant actions and behavior of the member nodes, e.g. to determine which CH it belongs to, and to send data to the CH
      Contains the process about how to determine the routing towards the sink in multi-hop scenario
    • Interface
      Contains the defination of all involved interfaces
    • Include
      Contains all header files
  • For a sink node
      Contains the configuration files and the wiring between interfaces
      Contains the actions and behavior of the sink
    • EMRSink.h
      Header file


The installation of EMR is rather simple and the following briefly introduces how the EMR resource could be loaded to the normal nodes and the sink node.

  • Then the user could copy the build folder and the Makefile into a new folder under the tinyOS directory for a normal node

  • Thirdly, copy the source code into a new folder for the sink node

  • Now, the user can load the binary code into normal nodes by
# make telosb reinstall.<node ID> bsl,/dev/ttyUSB*

  • And finally compile and load the binary code into sink nodes by
# make telosb install.100 bsl,/dev/ttyUSB*

Running EMR

The following describes about how to run the EMR routing solution step by step and how to test whether it is installed properly.

  • Operation
    • First, turn on all normal nodes. Please note that after a normal node is powered on, its red led will be on, meaning that this node is waiting for clustering indication from the sink node.
    • Then, turn on the Sink node.
    • When the sink node is on, the network starts operation, e.g. the CHs are selected, the clusters are organized and the data packets from the member nodes are collected by the CHs and are finally forwarded to the sink after data aggregation by the CHs.
    • Please note that as the operation of EMR is separated into rounds. During each round different CHs will be selected and different clusters will be formed. Therefore, during the operation, you should be able to see that from time to time, different leds of the nodes will be on, where a blue led means a CH, a green led means a member node and a red led means that this node has depleted its energy and died. Please note that each change of the led colour of the node means a novel round and the novel role that the node takes during this round. The following provides the status of the nodes during one specific round.

  • Monitor the debug messages

A user is able to use the serial output to watch the debug messages:

# java -comm serial@/dev/ttyUSB*:telosb 

The debug messages should start to be shown in the terminal as following:


  • Change parameters

A user is able to change the parameters, e.g. control_packet_size, data_packet_size freely in the funciton send_parameter() in the file For instance, the user could change the competetion range of the CH, smaller competetion range will generate more CHs and more blue led will be on during the network operation.


As an example, a demonstration of EMR can be set up by following steps:

Device deployment and demonstration tool

40 Telosb nodes are loaded with the EMR prototype program and deployed in a 5X8 matrix (as the picture shown in the section “Running EMR”). 1 Telosb node is loaded with the Sink program and placed on one side of matrix, e.g. on the right side.

In order to demonstrate not only the role of a node (Cluster Head or member) but also the status of node grouping , e.g. which cluster a member node joins, how big a cluster is, a GUI tool is created to show the distribution of clusters through the regular status messages reported by nodes. The network topology can be set freely by GUI users according to their needs.

The picture above is a snapshot of GUI display for a running EMR network. To facilitate the observation of users, some parameters can be customised, e.g. the node colour and shape, the ratio of node size, and the node information format.

The expectation of demonstration

During a demonstration, the following behaviours and performances are expected to be shown:

  • Autonomous clustering is shown by the nodes as members with the green LEDs on and Cluster Head (CH) with the blue LEDs on
  • The CH competition stage is indicated by the flashing green LEDs when clustering and routing solution is EMR and the nodes are qualified to be a CH candidates.
  • Because of CH competition, the number of CHs are stable and less than the number of expect CHs indicated by a ratio
  • Member nodes join clusters according to the distance to CHs and their remain energy
  • The amount of the remain energy is reflected by the node size in the GUI tool
  • Because of the EMR algorithm, the CHs closer to the Sink node have bigger coverage than those who are farer to the Sink node, and also have bigger cluster size and more member nodes in general
  • CHs marked as diamond shape in the GUI tool matches the CHs indicated by the blue LEDs of sensor nodes
  • Clusters are shown in different colours in the GUI tool. CHs are marked as diamond shape and members are marked as round shape
  • Node information is shown above each node in the GUI tool in the format of CH_ID/Remain energy/Round counting
  • The EMR solution and the classic clustering and routing solution can be activated respectively for each node of the network through altering the parameters on the Sink node.
  • The advantage of the EMR solution can be easily observed comparing to the classic clustering and routing solution: the distribution of CHs is more even and stable; the difference of the average energy consumptions for each node are much less over rounds; the first dead node appears much later in terms of time and number of round; the whole network survives longer
Last modified 12 years ago Last modified on Oct 26, 2010, 10:59:32 AM

Attachments (3)

Download all attachments as: .zip