Project 4 - Clustering

Due - Monday, October 20, 2008

There are several shortcomings of the program you wrote for Project 3.  First, during the off cycle, no sensing occurs.  This is useful for energy conservation, but limits the fidelity of the data collected.  Second, in-network data aggregation could provide additional energy savings.  The goal of this assignment is to implement a clustering algorithm to provide improved fidelity while maintaining limited energy usage.

For this assignment, you will implement a clustering algorithm similar to LEACH.  (If you haven't read the paper, do that now!)  Your algorithm will identify clusterheads that will remain continuously on to detect movement.  This provides increased fidelity (continuous sampling of the environment) with minimal additional overall energy cost.  

Periodically, as in Project 3, all nodes will turn on and spend 5 seconds detecting movement (the LISTEN period) followed by 15 seconds of deep sleep.  If movement is detected, a node will report the movement to its clusterhead, not to the base station.  Nodes need not report neighbor information to the base station as in Project 2.  The clusterhead will aggregate the movement detection information and send a report to the base station once per second.  The report will indicate whether there has been movement in the cluster.  In this way, fewer messages traverse the network to the base station and energy can be saved.

For undergraduates, the details of the algorithm are as follows:
  1. A new round begins every 4th LISTEN (80 seconds).
  2. At the beginning of the round, all nodes determine whether to become a clusterhead.  The decision is based on the preconfigured suggested percentage of clusterheads, the current round, and the clusterheads of previous rounds as described in the paper.  
  3. The nodes that have chosen to be clusterheads send a broadcast message with TTL 1 indicating their status.
  4. Each non-clusterhead determines which clusterhead to join based on the received signal strength (RSSI) of the message received.  Once a clusterhead is chosen, the transmit power for subsequent messages destined for the clusterhead can be set to the minimum level.
  5. When movement is detected, a node will unicast a message to its clusterhead. 
  6. Clusterheads will unicast a message to the base station regarding movement in its cluster every 1 second as described above.
Undergraduates may make the simplifying assumption that all nodes in the network are able to communicate with the base station.  Therefore, any node may choose to become a clusterhead.  

Graduate students must choose one of the following options:

It is strongly advised that you speak with me about your choice before you begin implementation.  Your grade will be based on the sophistication of your solution and minor extensions to the basic LEACH algorithm may not receive full credit.

Choice 1: Propose and implement an extension of the LEACH algorithm that works in a network where some sensors cannot communicate directly with the base station.  In other words, the algorithm must select clusterheads such that there is a path from any clusterhead to the base station, perhaps via other clusterheads.

Choice 2: Propose and implement another extension of the LEACH algorithm.  For example, you might design a way to integrate the battery life of the nodes into the selection of clusterheads.  

Choice 3: Perform some experimental analysis of the LEACH algorithm.  For example, you might compare several metrics (e.g. network lifetime) given different values of P (the preconfigured target percentage of clusterheads).

Choice 4: Implement the Span algorithm as described below:
  1. During LISTEN periods, a node will broadcast a HELLO message with a TTL of 1 every 1 second.  The message will contain the node's status (coordinator or not), its current coordinator, and its current neighbors.  Nodes will maintain this state about each neighbor.
  2. Every 4th LISTEN period (80 seconds), a node will determine whether to promote itself to be a coordinator using the eligibility rule described in the paper.  A node will announce this decision after the randomized backoff delay described in the paper.  If a node receives HELLO messages during the backoff period, it will reevaluate its own eligibility based on the same eligibility rule.
  3. Each non-coordinator determines which coordinator to join based on the received signal strength (RSSI) of the message received.
  4. Once a node has become a coordinator, it will remain a coordinator for 4 LISTEN periods (80 seconds) before deciding whether to withdraw.  As described in the paper, it will withdraw if every pair of its neighbors can reach each other either directly or indirectly.  After 8 LISTEN periods (160 seconds) as a coordinator, the coordinator will withdraw if every pair of neighbors can reach each other via some other neighbors.
  5. When movement is detected, a node will unicast a message to its clusterhead. 
  6. Clusterheads will unicast a message to the base station regarding movement in its cluster every 1 second as described above.

Due 3:30PM - Monday, October 20, 2008

  1. Complete and submit your working code. 
Note: No portion of your code may be copied from any other source including another text book, a web page, or another student (current or former). You must provide citations for any sources you have used in designing and implementing your program.
Sami Rollins