Saturday, October 8, 2011

References for Wireless Sensor Networks

I have referred various books , patents and IEEE papers to write articles in my blog on Wireless Sensor Networks. One can refer the below references for more and detailed information.

[1] Protocols and Architecture for wireless sensor network by H.Karl and A.Willig.

[2] Wireless Sensor Networks, Technology, Protocols and Applications by K.Sohraby, D.Minoli and T.Znati.

[3] A Survey on Sensor Networks by Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci.

[4] Routing in Mobile Wireless Sensor Networks by Andrea Munari and Wolfgang Schott.

[5] IEEE 802.15.4

[6] Distributed address assignment in ZigBee Protocol.

[7] Adaptive Protocols for Information Dissemination in Wireless Sensor Networks by Wendi Rabiner Heinzelman, Joanna Kulik, and Hari Balakrishnan.

[8] An Energy-Efficient MAC Protocol for Wireless Sensor Networks by Wei Ye, John Heidemann, Deborah Estrin.

[9] Energy-Efficient Communication Protocol for Wireless Microsensor Networks by Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan.

[10] Connecting Heterogeneous Sensor Networks with IP Based Wire/Wireless
Networks by Shu Lei, Wu Xiaoling, Xu Hui, Yang Jie, Jinsung Cho, and Sungyoung Lee.

[11] Unifying Micro Sensor Networks with the Internet via Overlay Networking by Hui Dai and Richard Han.

[12] Integrating Future Large-scale Wireless Sensor Networks with the Internet by Marco Z´u˜niga Z. and Bhaskar Krishnamachari.

[13] A Delay-Tolerant Network Architecture for Challenged Internets by Kevin Fall.

[14] Connecting Wireless Sensornets with TCP/IP Networks by Adam Dunkels,
, Juan Alonso, Thiemo Voigt, Hartmut Ritter, Jochen Schiller.

[15] Optimizing Sensor Networks in the Energy-Latency-Density Design Space by C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava.

[16] An Energy-Efficient Node Address Naming Scheme for Wireless Sensor Networks by Muneeb Ali and Zartash Afzal Uzmi.

[17] Dynamic Address Allocation for Management and Control in Wireless Sensor
Networks by Zheng Yao and Falko Dressler.

[18] Implementation and Evaluation of On-demand Address Allocation
for Event-Driven Sensor Network by Shinji Motegi, Kiyohito Yoshihara and Hiroki Horiuchi.

[19] A Novel Approach for Dynamic Address Assignment in Wireless Sensor Networks by Subba Reddy and Pavan Kumar B K.

[20] Fault-Tolerant Clustering of Wireless Sensor Networks by Gaurav Gupta and Mohamed Younis.

[21] Prolonging Sensor Network Lifetime with Energy Provisioning and Relay Node Placement by Y. Thomas Hou, Yi Shi, Hanif D. Sherali and Scott F. Midkiff.

[22] Deploying Sensor Networks with Guaranteed Capacity and Fault Tolerance by Jonathan L Bredin, Erik D Demaine, Mohammad Taghi Hajiaghayi, Daniela Rus.

[23] Fault Tolerance in Wireless Sensor Networks by Lakshmi Ramaswamy.

[24] Dynamic Power Management in Wireless Sensor Networks by Amit Sinha and Anantha Chandrakasan.

[25] Power Efficient Organization of Wireless Sensor Networks by Sasa Slijepcevic, Miodrag Potkonjak.

[26] Power Efficient Topologies for Wireless Sensor Networks by Ayad Salhieh, Jennifer Weinmann, Manish Kochhal.

[27] Wikipedia.

[28] Lease based Addressing for Event-Driven Wireless Sensor Networks by R. Chellappa Doss, D. Chandra, L. Pan, W.Zhou, and M. Chowdhury.

[29] QoS Support in Wireless Sensor Networks: A Survey, by Dazhi Chen and Pramod K. Varshney.

SPIN : Sensor Protocol for Information via Negotiation

SPIN stands for Sensor Protocol for Information via Negotiation. There is family of protocols called as SPIN; they come in different flavors and features. These protocols are designed to address the deficiency of flooding and gossiping.
SPIN uses three types of messages, ADV, REQ and DATA. The ADV message is broadcasted by a node which has some data. This message is broadcasted by the node. This message will say about type of data contained by the advertising node. Interested nodes which got the ADV message send REQ message requesting for the data. The node having the data sends the data to the interested nodes. The nodes after receiving data send ADV message, and the process continues. This can be seen in figure below.



SPIN protocol

Node 1 sends ADV message to all its neighbors, 2 and 3.Node 3 requests for the data using REQ message, for which node 1 send data using message DATA to node 3. After receiving the data Node 3 sends ADV message to its neighbors 4 and 5 and the process continues. It does not send to 1 because 3 knows that it received data from 1.
The data is described in the ADV packet using high level data descriptors, which are good enough to identify the data. These high level data descriptors are called meta-data. The meta-data of two different data’s should be different and meta-data of two similar data should be similar. The use of meta-data prevents, the actual data being flooded through out the network. The actual data can be given to only the nodes which need the data. This protocol also makes nodes more intelligent, every node will have a resource manager, which will inform each node about the amount various resources left in the node. Accordingly the node can make a decision regarding, whether it can as forwarding node or not.

Gossiping

Gossiping is similar to flooding except that, a node receiving a packet, instead of broadcasting, the node sends it to only one of its randomly selected neighbor, and the neighbor in turn sends the packet to one of its randomly selected neighbor, this continues until the packet reaches its destination. Gossiping reduces the number of packets in the network but the delay to reach destination in some cases may be very large. The diagram below shows gossiping.



Gossiping in WSN

Node 2 randomly selects node 1 among its neighbor to forward the packet, similarly node 1 selects node 4 among its neighbors, 2, 6, 5 and 4. Node 4 forwards the packet to 3.

Flooding

Flooding can be used for routing wireless sensor networks. In flooding, a node sends a packet received, to all its neighbors other than the neighbor which sent the packet to it, if the packet is not destined to itself or the maximum number of hops a packet can pass is not crossed. Flooding is very simple to implement, and it is reactive protocol, as it does not maintain any routing table (topology maintenance) and does not require discovering any routes. But this technique has several disadvantages, the most important being, it is responsible for large bandwidth consumption and it wastes valuable energy. This is not an energy aware protocol also. This protocol is not designed specifically for sensor networks. Similar data produced by nodes in the same region are also flooded, i.e. there is no data aggregation done. The diagram below gives an example for flooding.



Flooding in WSN

Node 2 sends a packet to node 1, which in turn sends the packet to all its neighbors, i.e. to node 3, node 4, and node 5. Node 1 does not send the packet to node 1 because node 1 knows that node 2 only sent the data to it.

Network Layer in Wireless Sensor Networks

Most of the data in the sensor network will be directed towards the sink. Special multi hop routing protocols are needed between sink and sensor nodes for wireless sensor networks. Most of the data conveyed to the sink form a sensor node will pass through many intermediate nodes before reaching the sink. Communicating data directly from the node to sink will be very energy expensive, so multi hop communication is preferred in wireless sensor network. The figure below makes the concept clearer.



Data form node N1 reaches sink through multiple intermediate nodes, N2, N3, and N4.

The network layer for sensor network is designed considering the following
1. Every protocol designed should be power efficient.
2. The protocol should support dynamic nature of sensor networks.
3. The sensor network protocols should make sensor network self configurable.
4. Data aggregation should be done, if it is advantageous.
5. Data centric design is more preferred, rather than address centric or location centric architecture.
There are several protocols and papers written regarding different issues in network layer for sensor networks, we shall understand a few in the proceeding sections.
A route form source to destination can be found based on many different criteria.



A scenario to explain different criteria that can be used to select a route form source (S) to Sink

One may choose a route which has maximum available power; in that case the route form source (S) to sink in the above diagram will be S-C-B-A- Sink. This is so because the power available in this route is 9, which is the highest compared to other routes.
One may go for route which consumes least power, and then the route selected can be S-B-A-Sink or S-D-Sink. S-D-Sink is preferred because less number of hops is present.
If the criterion to select is minimum number of hops then, the route S-D-Sink is selected.
There may other criteria that can be used, like a route with less probability of failure, a route less congested.
The routing may also be data centric routing. In this type of routing sink advertises the interest, and all nodes which have the data reply back to sink. Or it may be that all nodes advertise what kind of data they have, and other nodes which require that data request the node to give the data. In this type of routing, there is no importance given to a particular node but importance is given to the data or attribute. This type routing differs from the conventional routing schemes. Many papers and authors prefer data centric routing than conventional routing for sensor networks.
Data aggregation is done in sensor network to reduce the redundant data and hence save energy. For example in the figure shown before data from S and C is aggregated at node B, if the data form both C and S are almost similar. This reduces the amount data sent form B to A, hence conserves energy at B. Similarly data form A, D, E is aggregated at sink and sent further by sink, if the data has to be sent further. Data aggregation introduces delay in forwarding the data, as the node which aggregates the data has to wait for data from all nodes, to which the node aggregates the data. Even the process of aggregation consumes some amount of time.

Thursday, October 6, 2011

802.15.4 : An IEEE standard of Low Rate Personal Area Networks

802.15.4 is an IEEE standard of Low Rate Personal Area Networks. This standard covers Physical and MAC layer of Low Rate Personal Area Networks. Zigbee uses services provided by 802.15.4 and provides network constructions, security features and applications.

Two types of nodes are supported by this standard, FFD and RFD, which stand for Fully Functional Device and Reduced Functional Device. A FFD can act as coordinator or PAN coordinator or as a device. A RFD can only act as device. For more detailed description and understanding, of RFD and FFD one can refer to the standard itself.
A device must always be associated with a coordinator. The device has to communicate everything to the coordinator only. A coordinator can communicate with peer coordinators, and associated devices.

The standard offers two modes of operations; they are beaconed and non beaconed mode. The coordinator of a star network operating in the beaconed mode organizes channel access and data transmission with the help of a super frame structure shown below.



Super Frame structure in 802.15.4


The coordinator starts the superframe with the frame beacon packet, this will contains superframe specifications. The superframe has active and inactive periods. During inactive periods all nodes including the coordinator can sleep. They wake up just before the active period. The active period is divided into 16 slots, the first slot is used for beacon, and rests of slots are divided among the CAP and GTS.
The nodes operate using slotted CSMA-CA during CAP, the nodes can go to sleep mode during CAP if they do not have any data to receive or transmit. The nodes are active during GTS phase in their respective time slots. The coordinator is active throughout the active period.

All nodes send a request for GTS time slot during CAP to the coordinator. A field in the request packet specifies if the time slot is to transmit data to coordinator form the node or vice versa. There is also a field in the request packet, which specifies the number of GTS time slots required by the node. The coordinator specifies the slot allocated to the node using beacon frame.

If the node has been assigned slots to transmit data to the coordinator, then the node transmits data during that slot and it receives an acknowledgement for the same. If a slot is not assigned to the node and if the node wants to transmit data then, the node transmits data during CAP using slotted CSMA-CA and gets acknowledgement form the coordinator.

The coordinator sends any data it needs to send to a particular node, during node’s slot allocated. If it is not able to send during that slot then, the coordinator specifies that a data to be received is pending, in the beacon frame, by specifying the address of the node on which data is pending. The node requests for the same data during CAP using slotted CSMA-CA and the coordinator updates the data to the node.In non beaconed mode of operation, there is no GTS mechanism or beacon frame. All nodes operate in unslotted CSMA-CA mode and transmit and receive data.

CAP stands for contention access period, during this period all the nodes that want to communicate with the coordinator try to access the medium using slotted CSMA-CA protocol, the nodes request for some number of GTS form the coordinator during this CAP. The nodes also may send some data or receive some data during this period form the coordinator, if there was not slot assigned to the nodes. GTS stands for Guaranteed Time Slot, every node may have some slots assigned to them to receive or transmit data during this phase. One can refer to 802.15.4 for more detailed understanding of this standard.

Wednesday, October 5, 2011

LEACH : Low Energy Adaptive Clustering Hierarchy

LEACH stands for Low Energy Adaptive Clustering Hierarchy. This is a TDMA based protocol for wireless sensor networks with homogeneous nodes. LEACH is self organizing, adaptive clustering protocol. LEACH aims to distribute energy consumption at every node in the sensor network uniformly, aggregate data, i.e. support data fusion and localized coordination, between nodes to form and operate clusters.

All nodes in the network organize themselves into local clusters, with one node in the local cluster acting as cluster head. All nodes communicate only to the cluster head, and the cluster head conveys data to the base station. Nodes with higher capability advertise themselves as cluster heads, other nodes join the cluster head which is nearest to them. As cluster head has to spend lot of energy ,after certain time, randomized rotation of the cluster head is done, so that only node does not drain its energy. Every cluster head will prepare a schedule, to each of its members. The members communicate with the head only during that duration and sleep for the rest of the time. The diagram below shows the architecture of LEACH.



Architecture of LEACH

The operation of LEACH is broken into rounds. Each round starting with setup phase, during which clusters are formed and steady phase during which data is transferred to base station. Steady phase is longer than set up phase. Initially at the beginning of each round, each node decides if it has to be cluster head or not. The node which decides to be cluster head sends broadcasts a message. All other nodes will keep their receiver on and decide to which cluster head they need to join. Every node selects a cluster head which is nearest to it.

All nodes send messages to respective cluster heads. The cluster head based on the number of requesting node creates a TDMA schedule for all the nodes. Only during their respective schedules nodes interact with the cluster head, else the nodes will sleep.The cluster heads receives data form all nodes in its cluster, aggregates the data and sends it to the base station. The phase after the schedule is announced, is the steady phase and phase before schedule is announced, is setup phase. This can be seen in the diagram below. After the steady phase next round starts.



States in operation of LEACH

To avoid interference between clusters, all nodes in a cluster communicate using a CDMA code selected by the cluster head. There can also be hierarchy of clusters.

SMAC : Sensor MAC

SMAC stands for Sensor MAC . This protocol tries to reduce energy consumption due to overhearing, idle listening and collision. In this protocol also every node has two states, sleep state and active state. Unlike STEM, SMAC does not use two channels. A node can receive and transmit data during its listen period.

SMAC adopts a periodic wake up scheme. SMAC tries to synchronize the listen periods of neighboring nodes. The listen period of a node is divided into three phases as shown below. The listen period is the time during which a node is awake, rest of the time node is sleeping. The listen and sleep periods in the S-MAC are fixed intervals.



Three phases of listen period

In sync phase the neighboring synchronize their listen periods, a table is maintained regarding neighbors schedules, in RTS phase all nodes wishing to communicate to a particular node send RTS in CSMA mode with additional back off and in CTS the node acknowledges a particular RTS and communication between the two nodes starts and proceeds even in their sleep periods. The neighbors synchronize periodically.
SYNC packet is used to synchronize periodically. The SYNC packet contains senders address and time of its next sleep. The next sleep time is according to the sender, the receiver will adjust its timers after it receives the SYNC packet and updates the neighbor’s schedule.
In SMAC long data messages are fragmented and sent form transmitter to receiver. The receiver has to acknowledge for every fragment, else it is retransmitted. A series of fragments are sent with only one CTS and RTS message. This method is called as message passing. A protocol called T-MAC is proposed which is similar to S-MAC but with variable Listen and Sleep periods, this will help to suit the listen and sleep periods according to the load in the network.
The main concept in SMAC is that, all the neighboring nodes form virtual clusters and synchronize their sleep and listen periods. They communicate during their listen periods and sleep rest of the time. The immediate neighbors of nodes, which are transmitting and receiving, sleep until the communication is completed. A long message is divided into many fragments and all the fragments are sent as burst.
S-MAC contributes in these ways; reduction of idle listening(as nodes sleep and not stay in idle state),collision and overhearing avoidance by using RTS and CTS, and saving energy and time, by sending a series of fragments of a long message together, rather than going for contention after sending every fragment.

STEM: Sparse Topology and Energy Management

STEM stands for Sparse Topology and Energy Management. This protocol tries to save energy due to idle listening. This protocol does not provide a complete MAC protocol, however a MAC protocol can be used along with it to give a complete MAC protocol. This protocol proposes to use two channels, wake up channel and data channel. Wake up channel is used to inform the receiver that a transmitter wants to transmit data to it. Data channel is used to transmit data, underlying MAC protocol is used for this data transmission. STEM is designed for applications which wait for an event and report that event, when the event takes place. In other words STEM is applicable where nodes have two states, monitor sate, where nodes monitor and no event takes place, and transfer state, where event is detected and data has to be transmitted.
On the Wake up channel time is divided into sleep period and listen period, these together are called wake up period. This can be seen in the diagram below



Channels in STEM

There will be two transceivers in every sensor node. One is for wake up channel and other is for data channel. The transceiver of the data channel will always be in sleep mode until some has to received or transmitted by the node and the transceiver of the wake up channel will be sleep in sleep period and be active in listen period. During the listen period the wake up channel receiver is switched on and the node waits to check if any data is to be received if so the data channel transceiver is switched on or else the wake up channel transceiver goes to sleep.

The STEM protocol has two flavors; they are STEM-B and STEM-T. In STEM-B a node which wishes to transmit to another node, sends beacons periodically on the wake up channel. This beacon contains the address of transmitter and receiver. The receiver detects the beacons during its listen period and acknowledges the transmitter, and then both shift to data channel and exchange data. In STEM-T the transmitter sends busy tone on wake up channel for a long enough time to hit the receivers listen period. As there is no address of the receiver in the busy tone all neighboring nodes which hear busy shift to data channel, however on receiving the data, only the node for which the data was intended will reply and all others go back to sleep.

MAC Protocols for Wireless Sensor Networks

MAC layer is the layer immediately above the physical layer. In wireless networks many nodes contend use a single shared medium, the main function of the MAC layer is to regulate the access to this shared medium in such a way that all nodes are able to get their due. In other words the main duty of the MAC layer is to determine the time during which a node can send and receive, data, control and management packets. The MAC layer is a part of data link layer, other parts of data link layer are responsible for error and flow control.

The main challenge in designing MAC protocols for wireless sensor networks is to conserve as much energy as possible, as energy is present in the sensor nodes in very small quantity. So any MAC protocol designed should consider using energy present in the sensor nodes as less as possible.

The MAC protocols designed for wireless sensor networks have to necessarily consider all these problems, hidden station problem, exposed station problem, collisions because of multiple nodes accessing the medium together, noise added due to external interference, interference due to other systems working in similar frequency band, surge of data whenever event is detected, usage of as less energy as possible, sending control packets as less possible, keeping the overhead due to MAC headers and trailers as less as possible, keeping retransmission of packets as less as possible, low transmission delay, low access delay, and prioritize some critical packets.

The MAC protocols can be broadly divided into three categories, on demand assignment protocols, fixed assignment protocols and random access protocols. Examples for fixed assignment protocols are TDMA, FDMA, and CDMA. The protocols like CSMA, CSMA/CD, ALOHA, persistent and non persistent CSMA protocols are good examples for random access protocols. On demand assignment protocols assign resource to a node on demand and only for requested duration, after that the same resource may be given to some other requesting nodes. The on demand assignment protocols can be further classified into centralized and non centralized protocols. In centralized protocols a central server is responsible to assign all the requested resources in non centralized protocols all nodes by mutual understanding share the resources.
The most important issues to be considered to save energy are, over hearing, collisions, protocol overhead, idle listening. All these have to be as less as possible in all protocols designed for Wireless Sensor Networks and all protocols should be less complex in their operation and the foot print of the protocols should be small.

We shall understand some of the protocols designed for WSN in the next set of articles.