Here is a summary for the steps that this algorithm took to try and achieve coverage control for a mobile sensing network.
1. Each node calculates the voronoi partitions for itself and its neighbors
2. Use lloyd's algorithm to find the voronoi centroidal partition
3. Monitor for any nodes leaving or entering an area
4. Adjust sensing radius and communication radius
This process keeps going on as long as nodes are still moving around.
This algorithm looks like it was for sensor nodes that can control their movement as opposed to being attached to something that moves independently. So this type of protocol is for a very specific type of WSN that would most likely be very expensive to implement which to me is going against the reason you would use a WSN.
Tuesday, May 10, 2011
Variable Radii Connected Sensor Cover in Sensor Networks
This paper was very thorough in explaining everything that this protocol will do. It gave a list of all of the terms that are used throughout the paper that was very helpful for understanding what was going on.
This paper shows three different ways to obtain coverage using variable radii sensors. The method that they ended up saying was the best was the Voronoi based coverage method. This makes sense to me because all of the other coverage methods that they used required far more computations and this in turn made it cost more to use (energy costs). The Voronoi based approach outperformed all of the other protocols they presented.
This paper shows three different ways to obtain coverage using variable radii sensors. The method that they ended up saying was the best was the Voronoi based coverage method. This makes sense to me because all of the other coverage methods that they used required far more computations and this in turn made it cost more to use (energy costs). The Voronoi based approach outperformed all of the other protocols they presented.
Thursday, April 28, 2011
Secure routing for Mobile ad-hoc networks
MANET is self organised interconnection of wireless communication devies. The key challenge in mobile ad hoc networks is to provide security to the network becuase in the dynamic enviornment roaming nodes moves in and out of the network all the times that can bring malicious nodes to the network which can reroute or sometimes clog the n/w. So to avoid such scenario, authors presented a routing protocol that will mitigate the effects of such malicious nodes.Protocol fabricates consists of diverse paths from S-D.And also it is based on assumpation that there exists a shared key b'w source and destination. Source disperses the message into no of parts and each node is equipped with SRP header that consists of query identificaion number, Query sequence number and MAC. And once the data is received by destination node, It will validate the data by comparing it with information conatined in SRP header.
And in the end, Protocol guarantees thte route replies will never be rejected or reach back the querying node.
And in the end, Protocol guarantees thte route replies will never be rejected or reach back the querying node.
Routing Techniques in WSN- A survey-Part 4
GAF: Represents Gepgraphic ad aptive fidelity. In this protocol, Nodes already know thier location through GPS. Network is divided into grids. Set of nodes are assigned a grid, and optimize the sleep and active times w/out affecting routing fidelity and in this way energy is conserved therby increasing the n/w lifetime.
GEAR: Uses geographic attributes from data to route packets towards destinationinstead of using whole network. Learning and estimated costs are associated with each node and a hole is created in the region when node doesn't have a neighbor closer to target other than itself. Protocol consosts of two phases: Forwarding packet towards target region and Forwarding packet within region.
GOAFR: Its a combination of greedy and face roting algorithms.Greedy algorithm doesn't work best for non dense n/w's and OFR aims to find best node in n/w closer to destination.Thus by combining both of these algorithms it becomes optimal for both worst and average case efficiency.
SPAN: It selects nodes as coordinators based on position.Node becomes a coordinator if 2 neighbors can't reach each other directly.
Multipath routing protocol:It encourages the use of multiple path rather one single path.Introduced approach is to use path with highest residual energy until the energy falls below back up path after which back up path is used. In this way energy resources are maintained for long n/w lifetime.
Query based and Negotiation based routing:In query based, destination node sends query through network. Once the query is matched, node with data sends it to destination node.
Negotiation based routing uses high level data descriptors that eliminate redundant data transmission through negotiation.
Non coherent processing: Nodes will locally process raw data before being sent to other nodes for further processing. Consists of three phases: Target detection,Data collection and preprocessing,Memebership declaration and Central node election.
Coherent data processing: Data is forwarded to aggragators after min processing like time stamping, duplicate suppression.Also it is selected to perform energy efficient routing.
GEAR: Uses geographic attributes from data to route packets towards destinationinstead of using whole network. Learning and estimated costs are associated with each node and a hole is created in the region when node doesn't have a neighbor closer to target other than itself. Protocol consosts of two phases: Forwarding packet towards target region and Forwarding packet within region.
GOAFR: Its a combination of greedy and face roting algorithms.Greedy algorithm doesn't work best for non dense n/w's and OFR aims to find best node in n/w closer to destination.Thus by combining both of these algorithms it becomes optimal for both worst and average case efficiency.
SPAN: It selects nodes as coordinators based on position.Node becomes a coordinator if 2 neighbors can't reach each other directly.
Multipath routing protocol:It encourages the use of multiple path rather one single path.Introduced approach is to use path with highest residual energy until the energy falls below back up path after which back up path is used. In this way energy resources are maintained for long n/w lifetime.
Query based and Negotiation based routing:In query based, destination node sends query through network. Once the query is matched, node with data sends it to destination node.
Negotiation based routing uses high level data descriptors that eliminate redundant data transmission through negotiation.
Non coherent processing: Nodes will locally process raw data before being sent to other nodes for further processing. Consists of three phases: Target detection,Data collection and preprocessing,Memebership declaration and Central node election.
Coherent data processing: Data is forwarded to aggragators after min processing like time stamping, duplicate suppression.Also it is selected to perform energy efficient routing.
Tuesday, April 26, 2011
Reliable data transport and congestion control in wireless sensor networks-part1
One of the main challenges of WSN is reliable data transport. Reliable data delivery and congestion control are the two major functions in transport layer. Depending on the direction of data flow of data flow of the applications, the data transport can be classified into sensors-to-sink and sink-to-sensors. In this part I am going to give a brief over view of reliable data transport protocols.
PSFQ: This protocol guarantees reliable data delivery from sink-to-sensors. It comprises of three components: pump operation, fetch operation and report operation. It guarantees the reliability by fast fetching packets from neighboring nodes after a packet sequence gap is detected. It also deals with hop-by-hop loss recovery. Main drawback of PSFQ is use of in-sequence forwarding for message delivery to accomplish the pump slowly operation and this results in wastage of precious bandwidth.
RMST: Its primary goal is the delivery of large pieces of data to all subscribed sinks. RMST is NACK-based; it places responsibility for loss detection at the receivers (which can be intermediate nodes as well as the actual sinks). Missing fragments requests are uni cast from the sink to source. Caches in intermediate nodes allow for fast recovery. This scheme lacks in congestion control and energy efficiency.
GARUDA: Uses core-recovery idea to implement reliable downstream data delivery. Some nodes in the network play the role as loss recovery servers, and other non-core nodes need to have one-hop connection with at least one core nodes. GARUDA works in two-stage recovery. GARUDA's design is not optimized for very large messages and therefore it does not use features such as pipe lining which are critical fore reduced data propagation latency in large networks.
PSFQ: This protocol guarantees reliable data delivery from sink-to-sensors. It comprises of three components: pump operation, fetch operation and report operation. It guarantees the reliability by fast fetching packets from neighboring nodes after a packet sequence gap is detected. It also deals with hop-by-hop loss recovery. Main drawback of PSFQ is use of in-sequence forwarding for message delivery to accomplish the pump slowly operation and this results in wastage of precious bandwidth.
RMST: Its primary goal is the delivery of large pieces of data to all subscribed sinks. RMST is NACK-based; it places responsibility for loss detection at the receivers (which can be intermediate nodes as well as the actual sinks). Missing fragments requests are uni cast from the sink to source. Caches in intermediate nodes allow for fast recovery. This scheme lacks in congestion control and energy efficiency.
GARUDA: Uses core-recovery idea to implement reliable downstream data delivery. Some nodes in the network play the role as loss recovery servers, and other non-core nodes need to have one-hop connection with at least one core nodes. GARUDA works in two-stage recovery. GARUDA's design is not optimized for very large messages and therefore it does not use features such as pipe lining which are critical fore reduced data propagation latency in large networks.
Routing Techniques in Wireless Sensor Networks: A Survey - Part2
Directed Diffusion: It is a data-centric application paradigm where Base Station (BS) broadcasts the interests and sources will reply to the interests. Even though this protocol is very popular it has its own drawbacks. This is unsuitable for one-time queries, is not applicable to applications that require continuous data delivery to the BS and is not energy efficient.
Rumor Routing: This protocol floods the events rather than queries and each node maintains an event table and generated agent which propagate information to distant nodes. This protocol is energy-efficient and handles node-failures but doesn't work well when number of events is large.
MCFA: This algorithm exploits the fact that the direction of routing is always known and nodes doesn't have to maintain a routing table. In this each message is broadcasted to its neighbors and node checks if it is on the least-cost path between the sensor node and the base station.
Gradient-Based Routing (GBR): Key idea of this protocol is to memorize the height of the node (min number of hops) to the base station when interest is diffused. GBR uses data aggregation and traffic spreading to uniformly divide the traffic over the network. Three different data dissemination techniques are discussed in GBR, Stochastic scheme, Energy-based scheme and Stream-based scheme.
COUGAR: This protocol adds a query layer that lies between the network and application layers. Sensor nodes select a leader node to transmit the data. Base Station generates a query plan which specifies the flow of data and selection of leader to a query. In this protocol, addition of query layer to each node is an overhead and leader nodes should be dynamically maintained to prevent them from being hot-spots.
ACQUIRE: This protocol divides complex queries into sub-queries. When BS sends query each node tries to respond to query before forwarding it to another node. This protocol is not evaluated through simulations.
Energy-Aware Routing: The main objective of this protocol is to increase network lifetime. In this set of paths are maintained based on energy-levels. Route set up is complicated in this protocol.
LEACH : In this few nodes act as cluster head nodes and these nodes are rotated. This protocol is operated in two-phase. In setup phase clusters are organized and cluster heads are selected. In steady phase data is transferred to base station. Some issues with LEACH are, assumes all nodes can transmit with enough power and also assumes that cluster heads consume same energy as non-cluster head nodes.
Monday, April 25, 2011
Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures
The paper highlights the importance of security mechanisms in wireless sensor network routing protocols. The authors point out that adding security to a routing protocol after the design is complete is very difficult due to the limited processing capabilities of the sensor nodes and hence, security should be incorporated as one of the design parameters of a routing protocols. Various security threats and their counter measures, for both generic and specific routing protocols have been discussed.
Subscribe to:
Posts (Atom)