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:
- A new round begins every 4th LISTEN (80 seconds).
- 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.
- The nodes that have chosen to be clusterheads send a broadcast message with TTL 1 indicating their status.
- 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.
- When movement is detected, a node will unicast a message to its clusterhead.
- 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:
- 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.
- 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.
- Each non-coordinator determines which coordinator to join based on the received signal strength (RSSI) of the message received.
- 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.
- When movement is detected, a node will unicast a message to its clusterhead.
- 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
- 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