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.
Saturday, October 8, 2011
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.
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.
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.
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.
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.
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.
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.
Subscribe to:
Posts (Atom)
