Multihop Wireless Sensor Network Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this report, the design and implementation of the dynamic self organizing ad hoc network is presented. The network architecture is based on the cluster tree topology. It uses the gossip based protocol for communication between its nodes. The nodes periodically collect the acoustic changes in the environment and relay it to the gateway node.


A wireless sensor network is a collection of nodes organized into a cooperative network. Each node consists of processing capability (one or more microcontrollers, CPUs or DSP chips), may contain multiple types of memory (program, data and flash memories), have a RF transceiver (usually with a single omni-directional antenna), have a power source (e.g., batteries and solar cells), and accommodate various sensors and actuators.

It generally consists of a base station (or "gateway") that can communicate with a number of wireless sensors via a radio link. Data is collected at the wireless sensor node, compressed, and transmitted to the gateway directly or, if required, uses other wireless sensor nodes to forward data to the gateway. The transmitted data is then presented to the system by the gateway connection.

Wireless sensor networks are a trend of the past few years, and they involve deploying a large number of small nodes. The nodes then sense environmental changes and report them to other nodes over flexible network architecture. Sensor nodes are great for deployment in hostile environments or over large geographical areas.

The basic issue in communication networks is the transmission of messages to achieve a prescribed message throughput and Quality of Service (QoS). QoS can be specified in terms of message delay, message due dates, bit error rates, packet loss, economic cost of transmission, transmission power, etc. Depending on QoS, the installation environment, economic considerations, and the application, one of several basic network topologies may be used.

Usage of sensor networks

Sensor networks have been useful in a variety of domains. The primary domains at which sensor are deployed follow:

Environmental observation. Sensor networks can be used to monitor environmental changes. An example could be water pollution detection in a lake that is located near a factory that uses chemical substances. Sensor nodes could be randomly deployed in unknown and hostile areas and relay the exact origin of a pollutant to a centralized authority to take appropriate measures to limit the spreading of pollution. Other examples include forest fire detection, air pollution and rainfall observation in agriculture.

Military monitoring. Military uses sensor networks for battlefield surveillance; sensors could monitor vehicular traffic, track the position of the enemy or even safeguard the equipment of the side deploying sensors.

Building monitoring. Sensors can also be used in large buildings or factories monitoring climate changes. Thermostats and temperature sensor nodes are deployed all over the building's area. In addition, sensors could be used to monitor vibration that could damage the structure of a building.

Healthcare. Sensors can be used in biomedical applications to improve the quality of the provided care. Sensors are implanted in the human body to monitor medical problems like cancer and help patients maintain their health.

On the whole, the wireless sensor network provides low cost and wide application range. It also allows convenient monitoring of the remote areas.

State of Art

The design of the multihop network requires efficient addressing and routing scheme. The disjoint address allocation scheme [1] is studied for address allocation of the nodes. Each node in MANET keeps disjoint address set and hands over a half of its set to new joining node. The address allocation depends on the state of the neighbor node. When at least one neighbor node has enough address to hand over, the new node can obtain its address set from the neighbor. This process is called local allocation otherwise the new node has to look for remote node with enough address.

When all neighbor nodes have only their own address, the new node sends message to one of its neighbor. The neighbor node broadcast message to look for node with more than one address. Upon receiving the message each node replies back unicast message to inform its address set. Then the agent picks the node with the largest set and allocates half of the set to the requester.

The main limitation of this approach is inefficient utilization of the address space.

The nodes are biased to certain area of the MANET; address set can be unevenly distributed. Therefore some nodes suffer from the lack of the address while other have enough address.

Address space of the MANET is distributed and maintained by the individual nodes; address can be wasted when node leaves the network without returning their address space.

This process for collecting the unoccupied address is triggered when agent does not receive any response in remote allocation process. The agent flood message for requesting the current occupied address. Upon receiving the request, each node forwards the request and set its timer for response. Then it waits for response from its neighbor until the timer expires. After the time-out it sends one hop broadcast message containing cumulative address set which is union set of its address and address set from neighbor.

In addition, scalable distributed address allocation protocol for ad hoc network [2] is studied for addressing the nodes. Dynamic address allocation techniques can be broadly classified into three categories. Decentralized address assignment algorithms view address allocation as a distributed agreement problem. Each node independently chooses a network address and validates the address with approval from all nodes in the network. In leader based approaches, nodes obtain the address from an elected leader responsible for address assignment. Both decentralized and leader based approaches guarantee unique address assignment. In best effort address assignment methods, nodes assign their own addresses without approval of other nodes. Hence there is a potential for duplicate address assignment in best effort services and a duplicate address detection mechanism is often employed to detect duplicate addresses.

The node initiating the network will obtain an IP address by DHCP or IPAA and will be called the Root Node. The Root Node will also be the Cluster Head for the first network and it will assign itself a dynamic address of 01: FE. Here, 01 represents the network ID (cell ID) and FE is the node ID. The dynamic address is composed of a network ID identifying a network cell, and a node ID identifying a node within the cell. All Cluster Heads in the system are assigned an address of XX: FE in their respective networks, where XX is the network ID assigned by the Root Node. The addresses XX: FF and XX: 00 are reserved for local broadcast to a network cluster XX. Similarly the address FF: FF is reserved for network wide broadcast.

In addition, to the address allocation routing scheme are also studied for traversing the packets across the network. The routing in WSNs can be divided into flat-based routing, hierarchical-based routing, and location-based routing depending on the network structure. In flat-based routing, all nodes are typically assigned equal roles or functionality. In hierarchical-based routing, however, nodes will play different roles in the network. In location-based routing, sensor nodes' positions are exploited to route data in the network. In addition to the above, routing protocols can be classified into three categories, namely, proactive, reactive, and hybrid protocols depending on how the source finds a route to the destination.

In flat networks, each node typically plays the same role and sensor nodes collaborate together to perform the sensing task. Due to the large number of such nodes, it is not feasible to assign a global identifier to each node. This consideration has led to data centric routing, where the BS sends queries to certain regions and waits for data from the sensors located in the selected regions.

In a hierarchical architecture, higher energy nodes can be used to process and send the information while low energy nodes can be used to perform the sensing in the proximity of the target. This means that creation of clusters and assigning special tasks to cluster heads can greatly contribute to overall system scalability, lifetime, and energy efficiency. Hierarchical routing is an efficient way to lower energy consumption within a cluster and by performing data aggregation and fusion in order to decrease the number of transmitted messages to the BS.

In the location based routing, sensor nodes are addressed by means of their locations. The distance between neighboring nodes can be estimated on the basis of incoming signal strengths. Relative coordinates of neighboring nodes can be obtained by exchanging such information between neighbors. Alternatively, the location of nodes may be available directly by communicating with a satellite, using GPS (Global Positioning System), if nodes are equipped with a small low power GPS receiver. To save energy, some location based schemes demand that nodes should go to sleep if there is no activity.

Moreover, the election of the cluster head is critical as it decides the longevity of the Network. Many researchers have come up with algorithm for deciding the cluster head. One way is using the probabilistic approach for deciding the cluster head among the nodes. However, such approach may reduce the network lifetime because it does not consider the distribution of sensor nodes and the energy remains of each node.

Based on the literature survey we designed a dynamic scalable hierarchal address allocation scheme. The addressing scheme is essential as it decides the size of the routing table and efficiency of the routing scheme. In cluster head topology, the cluster head assign the address to its child members. However, the cluster head address is given by centralized node. This helps in prevents the conflict in deciding the cluster head address. Moreover, the address allocation is scalable which prevents the increase in size of address with increase of the nodes.

In the Gateway selection process, a node turns on and listens for the INVITATION message from other nodes. If it can't get any messages for certain time, then it turns to a gateway and sends out an INVITATION message to its neighbors. For the Cluster head selection process, if the child node receives the join request message then it will request for the cluster assignment address to the gateway node and it will assign the address to the cluster head.

The routing algorithm is based on the gossip protocol. In literal sense, it means relay the packet from the child node to the parent node and from the parent node to the child node. In order to implement this protocol each node has to maintain the table of its child and table for the parent node. On knowing the next hop address the packet gets traversed from child node to the gateway and from gateway to the child node.

System Architecture

Fig 1: System architecture of the sensor network

The figure 1 illustrates the network infrastructure of the multi hop Network. The child nodes are connected to the cluster head node and the cluster head node is connected to the gateway node.

A network node may be in one of two possible roles:

Gateway Node

Cluster Head Node

Child Node

The Network get branched off from the gateway node. Any new node will join as the child node and start transmitting the invitation packets to grow the existing network. If other new node wants to join the network it will send the join request to the previous child node. Now the previous child node becomes the cluster head node and assigns address to the new node. The behavior of the gateway node, cluster head node and child nodes are described below.

Gateway Node:

It initializes the radio interface for sending and receiving packets.

It then fires the Timer 0 to send the invitation packets every one second.

It will listen for the join request packet and get the globally unique id from the child node.

It uses the value of the counter and the gateway node address to assign the child node address.

Then it sends assigned address in the acknowledgement packet.

It will start listening for the data packets send from the end node.

While receiving the data packets, using the CC2420 interface it gets the RSSI and LQI values.

In addition, to the RSSI and LQI value it also receives the acoustic sensor data from the child nodes.

It creates the table for storing the end node ID, RSSI, LQI and acoustic sensed values.

On receiving the data packets it stop the invitation timer.

While receiving the data packet, it relay the sensor data to the serial port using the AM Serial interface.

Moreover, it also receives the fragmented file data from the end node.

It also listens for the cluster head request message from the parent node and assigns the unique routing address to the parent node.

This routing address is sent to the parent node through the assign cluster head message.

Cluster Head Node:

It initializes the radio interface and listens on this interface.

It will listen for the invitation packets in order to join the network.

After receiving the invitation packet, it sends the join request packet contain globally unique ID.

It waits for the acknowledgment packet from the root node which provides the assign address from gateway node.

Receiving the acknowledgment packet, it fires the timer 0, timer 2, and timer 3 for sending the data packets every five seconds, invitation packets every second and fragmented file data every 0.55 second respectively.

On receiving the join request message from the child node it send the cluster head request message to the gateway node.

It receives the assign cluster message it uses the assigned address and allocates the address to the child node.

While receiving the data packets from the child node, it stops the invitation timer and file data timer.

On receiving the data packet and fragmented file data from the child node it relays the packet to the gateway node.

Child Node:

It initializes the radio interface and listens on this interface.

It will listen for the invitation packets in order to join the network.

After receiving the invitation packet, it sends the join request packet contain globally unique ID.

It waits for the acknowledgment packet from the parent node which provides the assign address.

Receiving the acknowledgment packet, it fires the timer 0, timer 2 and timer 3 for sending the data packets every five seconds, invitation packets every second and fragmented file data every 0.55 seconds respectively.

Gateway Node Architecture

Fig 2: Gateway Node Architecture

The fig 2 illustrates the architecture of the gateway node. It shows the means of relaying the data packet received from the cluster head to the PC via the serial port. The gateway received the data packet containing the sensor values from the network using RF module. This module is utilized using the AMReceive interface and forwarded to the gateway code. It then forwards the sensor data field to the Serial packet and sends it to the serial port. It uses the AMSerial send interface for transmitting the serial packet to the serial port. Moreover, the gateway node can send the data packet to the nodes using AMSend interface via RF module. The gateway code on receiving the data packet uses the CC2420 chip for measuring the RSSI and LQI values for estimating the link quality.

Cluster Head / Child Node Architecture

Fig 3 Cluster Head / Child Node architecture

The fig 3 illustrates the Cluster head / Child node architecture for transmission of the radio packets and sensing the acoustic sound. It uses the MTS 300 sensor board from the crossbow technology for sensing the acoustic sound from the environment. It uses the MicC component and read interface for sensing the acoustic sound. In addition, it uses the AMSend and AMReceive interface for sending and receiving the radio packets via the RF interface respectively.

Address Allocation Procedure

If the node is the gateway then it is assigned the address of 0x2525

On receiving the join request message from the child node it increments the counter value. Using the counter and its assign the address to the child node e.g. 0x2501.

If other node joins the gateway then it will assign address as 0x2502.

Now if the child node 0x2501 receives the join request from the new node, the gateway node assigns routing address as 0x0125.

On receiving the routing address the cluster head node increments counter for assigning address its child node e.g. 0x0101.

Hence in this way the address allocation is done.


The network nodes are implemented in the TinyOS. It is a free and open source component-based operating system and platform targeting wireless sensor networks (WSNs). TinyOS started as collaboration between the University of California, Berkeley in co-operation with Intel Research and Crossbow Technology, and has since grown to be an international consortium, the TinyOS Alliance.

TinyOS is an embedded operating system written in the nesC programming language as a set of cooperating tasks and processes. It features a component-based architecture which enables rapid innovation and implementation. Moreover, it is an event based operating environment designed for use with embedded networked sensors. More specifically, it is designed to support the concurrency intensive operations required by networked sensors with minimal hardware requirements. The programming language of TinyOS is stylized C that uses a custom compiler 'NesC'.

The motes used for the implementation of the above shown system architecture are the Micaz.

Fig 4 Schematic of the Micaz mote

The following presents the specification of the Micaz mote

Microprocessor: Atmel ATmega128L

7.3728 MHz clock

128 kB of Flash for program memory

4 kB of SRAM for data and variables

2 UARTs (Universal Asynchronous Receive and Transmit)

Serial Port Interface (SPI) bus

Dedicated hardware I2C bus

Radio: Chipcon's CC2420

External serial flash memory: 512 kB

51-pin expansion connector

Eight 10-bit analog I/O

21 general purpose digital I/O

User interface: 3 programmable LEDs

JTAG port

Powered by two AA batteries

1850 mAH capacity

Sequence Diagram for communication between the Gateway, Cluster head and Child Node

Fig 5 Sequence diagram for the network node

Activity Diagram for Gateway, Cluster Head and Child Node

Fig 6 Activity Diagram


First the node starts the radio interface for sending or receiving the packets.

After successfully starting the radio it starts the one shot timer 1 for deciding whether it is gateway or the child Node.

If the node does not receives any invitation packets before the timer 1 expires (Five Seconds) then it consider itself to be gateway node. Otherwise, if it receives the invitation packet within the duration then it considers itself to be child Node.

If is the gateway then it fires the timer 0 for sending the invitation packets every second.

The child listens to the radio interface for receiving the invitation packets.

If it is not registered it sends the join request message with the globally unique ID.

The root will listen to the channel and check for the destination address of the received packet.

If it is the join request packet then it uses the counter and the gateway address to assign the address to the child node.

It sends the assign address with the acknowledgment packet to the end node.

On receiving the acknowledgment packet at the end node, it fires the timer 0 to send the data packets every five seconds, timer2 to start the invitation packet and timer3 for sending the fragmented file packet.

The Child node sends the acoustic sensor value in the data packet.

The gateway node listens for the data packets and gets RSSI, LQI and acoustic sensor values. It generates the table for storing the RSSI, LQI, Node ID and acoustic sensor value. On receiving the data packet the gateway stops the invitation timer.

As the child node started sending the invitation packet it comes in the role of becoming potential parent.

If the child node receives the join request message it sends the cluster request message to the gateway node to become the cluster head.

In response the gateway node sends the cluster assign message to the requested child node to allocate new routing address.

The child node sends the acknowledgement packet giving the address to the new node.

The new node receiving acknowledgement start timer 0 for sending the data to the parent and timer 2 for sending the invitation packet and timer 3 for sending the fragmented file data.

The cluster head node on receiving the data packet stops its invitation timer and the file packet timer.

On receiving file and data packet from the child node the parent node relay the packet to the gateway node.

Hence, in this way the sensor network keeps on growing network based on the cluster tree topology

Shortcoming of the Protocol

If the child node does not receive the acknowledgment for the join request sent then the child node will not sent the data packets to the root node. So there should be timer at the end node if it does not receive the acknowledgment then it again sent the join request to the root node.

There should be some handshaking mechanism for synchronization of timing between the child node and gateway node before actual transmission of data.

The frequency of the invitation packet can be reduced so as to reduce the network congestion.

If the child node wants to sleep for some amount of time then it should sent the sleep packet to gateway node.

There should be some level of encryption of the data packets should be provided to avoid information leakage.

There should be mechanism for aggregation of the data packet at the child node and send it all in one packet to save power and network congestion.


Invitation Packet: Gateway, Parent or child sends the invitation packets for inviting the potential node to join the network.

Join Packet: The Child node sends the join request packet to join the network and conveys its globally unique ID.

Acknowledgment Packet: The gateway or the parent node sends the acknowledgment to the child node providing the assign id to the child node.

Data Packet: The child node sends the data packet to its parent node and measures the RSSI and LQI values.

Cluster request Packet: The potential parent node sends the Cluster request message to the gateway to get new routing address.

Cluster Assign Packet: The gateway node sends the cluster assign message to the parent node giving new routing address.

File Packet: It is used to send the fragmentation of the file to the gateway node.

Results observe on the Hercules Software


The project required comprehensive understanding of the address allocation scheme, routing of the packets and election of the cluster head before actual implementation. Micaz motes provides flexible interface of the sensor boards with the help of components and interface modules. On the whole, TinyOS provides good platform for designing the dynamic ad hoc scalable sensor network.