mhleachpsm.nc

Tinyos LEACH protocol modify

/*
* MHLeachPSM.nc - The LEACH logic for multihop messaging
*
* @author Geoff Martin
* @date 18th April 2004
* @version 1.0
*/
includes AM;
includes MH;
module MHLeachPSM
{
	provides
	{
		interface StdControl;
		interface RouteSelect;
	}
	uses
	{
		interface Timer as RoundTimer;
		interface Timer as StatusTimer;
		interface ReceiveMsg;
		interface SendMsg;
		interface Random;
		interface Leds;
	}
}
implementation
{
/*---------------------------------------------------------------------
* Types and Variables
*---------------------------------------------------------------------*/
/*
* Type Definitions
*/
  typedef struct RoutePacket
  {
    // If addr is the broadcast address treat as a status message,
    // If addr is a specific node address treat as a forwarding request
    uint16_t addr;
    uint16_t nodeID;
    uint16_t depth;
    uint8_t round;
    bool isClusterHead;
    // This field is used to request that a node becomes a cluster head for forwarding
    bool becomeClusterHead;
  } __attribute__ ((packed)) RoutePacket;

  typedef struct NeighbourTable
  {
    uint16_t nodeID;
    bool isClusterHead;
    uint16_t depth;
    uint8_t timerTicks;
    bool nodeAlive;
    uint16_t strength;
  } NeighbourTable;

/*
* Constant Definitions
*/
  enum
  {
    ROUND_LENGTH = LEACH_ROUND_LENGTH,
    ROUTE_UPDATE_RATE = LEACH_ROUTE_UPDATE_RATE,
    NEIGHBOUR_TABLE_SIZE = LEACH_NEIGHBOUR_TABLE_SIZE,
    NEIGHBOUR_DEAD_TICKS = 5,
    TIMEOUT_TICKS = 5, // Ticks before requesting a node becomes a cluster head
    PARENT_INVALID = 0xeeee,
    INFINITY = 0xffff,
    ROUND_INVALID = 0xff,
    PROBABILITY = LEACH_PROBABILITY
  };
/*
* Node state
*/
  uint8_t round; // Current LEACH round
  uint16_t parentID;
  bool isClusterHead;
  uint16_t depth; // Depth of node in tree
  uint8_t ticks; // Number of ticks without connecting to a cluster head
  TOS_Msg routeMsg; // TOS_Msg to store routing information
  bool sendRouteBusy; // Flag to indicate send status
  uint16_t addr; // Address for use in forwarding requests
/*
* Neighbour table and state
*/
	NeighbourTable neighbours[NEIGHBOUR_TABLE_SIZE];
	uint16_t tableEntries;
/*---------------------------------------------------------------------
* Route table update and parent select
*---------------------------------------------------------------------*/
// Update route table
  static void updateTable()
  {
    int i;
    for (i = 0; i < tableEntries; i++)
    {
      // Only update ticks if node is alive - this avoids infinite ticks
      if (neighbours[i].nodeAlive == TRUE)
      {
        neighbours[i].timerTicks++;
        if (neighbours[i].timerTicks >= NEIGHBOUR_DEAD_TICKS)
        {
          dbg(DBG_TEMP, "MHLeachPSM - Setting node %i as dead in neighbour table\n", neighbours[i].nodeID);
          neighbours[i].nodeAlive = FALSE;
	}
      }
    }
    if (isClusterHead == TRUE) {
      atomic {
        call Leds.greenOn();
      }
    }
    else {
      atomic {
        call Leds.greenOff();
      }
    }
  }

// Update table entry
  static void updateTableEntry(uint16_t id, uint16_t treeDepth, bool isHead, uint16_t strength)
  {
    int i;
    // Search table for entry, dead nodes and highest hop entry
    uint16_t maxLeafDepth, maxHeadDepth;
    int maxLeafIndex, maxHeadIndex, nodeDead;
    maxLeafDepth = maxHeadDepth = 0; // Only node 0 has depth 0
    maxLeafIndex = maxHeadIndex = nodeDead = tableEntries;
    for (i = 0; i < tableEntries; i++)
    {
      // If the node has an entry
      if (neighbours[i].nodeID == id)
      {
        break;
      }
      // Else if the node is dead
      else if ((neighbours[i].nodeAlive == FALSE) && (nodeDead == tableEntries))
      {
        nodeDead = i;
      }
      // Else if the node is a cluster head and has the highest depth so far
      else if ((neighbours[i].isClusterHead == TRUE) && (neighbours[i].depth > maxHeadDepth))
      {
        maxHeadDepth = neighbours[i].depth;
        maxHeadIndex = i;
      }
      // Else if the node is a leaf and has the highest depth so far
      else if (neighbours[i].depth > maxLeafDepth)
      {
        maxLeafDepth = neighbours[i].depth;
        maxLeafIndex = i;
      }
    }
    // Update old entry
    if (i < tableEntries)
    {
      dbg(DBG_TEMP, "MHLeachPSM - Updating node %i in neighbour table\n", id);
      neighbours[i].isClusterHead = isHead;
      neighbours[i].depth = treeDepth;
      neighbours[i].timerTicks = 0;
      neighbours[i].nodeAlive = TRUE;
      neighbours[i].strength = strength;
    }
    // Replace dead entry
    else if (nodeDead != tableEntries)
    {
      dbg(DBG_TEMP, "MHLeachPSM - Replacing dead node %i with node %i in neighbour table\n",
      neighbours[nodeDead].nodeID, id);
      neighbours[nodeDead].nodeID = id;
      neighbours[nodeDead].isClusterHead = isHead;
      neighbours[nodeDead].depth = treeDepth;
      neighbours[nodeDead].timerTicks = 0;
      neighbours[nodeDead].nodeAlive = TRUE;
      neighbours[nodeDead].strength = strength;
    }
    //If there is space in the table for a new node
    else if (tableEntries < NEIGHBOUR_TABLE_SIZE)
    {
      dbg(DBG_TEMP, "MHLeachPSM - Adding node %i to neighbour table\n", id);
      neighbours[tableEntries].nodeID = id;
      neighbours[tableEntries].isClusterHead = isHead;
      neighbours[tableEntries].depth = treeDepth;
      neighbours[tableEntries].timerTicks = 0;
      neighbours[tableEntries].nodeAlive = TRUE;
      neighbours[tableEntries++].strength = strength;
    }
    // Replace leaf node with cluster head node
    else if ((isHead == TRUE) && (maxLeafIndex != tableEntries))
    {
      dbg(DBG_TEMP, "MHLeachPSM - Replacing leaf node %i with cluster head %i in neighbour table\n",
      neighbours[maxLeafIndex].nodeID, id);
      neighbours[maxLeafIndex].nodeID = id;
      neighbours[maxLeafIndex].isClusterHead = isHead;
      neighbours[maxLeafIndex].depth = treeDepth;
      neighbours[maxLeafIndex].timerTicks = 0;
      neighbours[maxLeafIndex].nodeAlive = TRUE;
      neighbours[maxLeafIndex].strength = strength;
    }
    // Replace leaf node with leaf node of lower depth
    else if ((maxLeafIndex != tableEntries) && (maxLeafDepth > treeDepth))
    {
      dbg(DBG_TEMP, "MHLeachPSM - Replacing leaf node %i with leaf node %i in neighbour table\n",
      neighbours[maxLeafIndex].nodeID, id);
      neighbours[maxLeafIndex].nodeID = id;
      neighbours[maxLeafIndex].isClusterHead = isHead;
      neighbours[maxLeafIndex].depth = treeDepth;
      neighbours[maxLeafIndex].timerTicks = 0;
      neighbours[maxLeafIndex].nodeAlive = TRUE;
      neighbours[maxLeafIndex].strength = strength;
    }
    // Replace cluster head with cluster head closer to base station
    else if ((isHead == TRUE) && (maxHeadIndex != tableEntries) && (maxHeadDepth > treeDepth))
    {
      dbg(DBG_TEMP, "MHLeachPSM - Replacing cluster head %i with cluster head %i in neighbour table\n", neighbours[maxHeadIndex].nodeID, id);
      neighbours[maxHeadIndex].nodeID = id;
      neighbours[maxHeadIndex].isClusterHead = isHead;
      neighbours[maxHeadIndex].depth = treeDepth;
      neighbours[maxHeadIndex].timerTicks = 0;
      neighbours[maxHeadIndex].nodeAlive = TRUE;
      neighbours[maxHeadIndex].strength = strength;
    }
  }
  
  // Select parent
  static void selectParent()
  {
    int i;
    uint16_t minLeafDepth, minHeadDepth;
    int minLeafIndex, minHeadIndex;
    ticks++;
    minLeafDepth = minHeadDepth = INFINITY;
    minLeafIndex = minHeadIndex = tableEntries;
    for (i = 0; i < tableEntries; i++)
    {
      // If node is a cluster head and has the lowest depth
      if ((neighbours[i].isClusterHead == TRUE) && (neighbours[i].depth < minHeadDepth))
      {
        minHeadDepth = neighbours[i].depth;
        minHeadIndex = i;
      }
      // Else if node is a leaf and has the lowest leaf depth
      else if (neighbours[i].depth < minLeafDepth)
      {
        minLeafDepth = neighbours[i].depth;
        minLeafIndex = i;
      }
    }
    // Choose the lowest depth cluster head
    if (minHeadIndex != tableEntries)
    {
      parentID = neighbours[minHeadIndex].nodeID;
      depth = neighbours[minHeadIndex].depth + 1;
      ticks = 0;
      dbg(DBG_TEMP, "MHLeachPSM - New parent selected (ID: %i)\n", parentID);
      return;
    }
    // If timeout has occurred request forwarding from connected leaf node
    else if (ticks >= TIMEOUT_TICKS)
    {
      // Ask a node to become a cluster head every TIMEOUT_TICKS if a suitable node exists;
      if (minLeafIndex != tableEntries)
      {
        atomic addr = neighbours[minLeafIndex].nodeID;
      }
      ticks = 0; // Set ticks to 0 to restart timeout
    }
    parentID = PARENT_INVALID;
    dbg(DBG_TEMP, "MHLeachPSM - Could not select new parent\n");
    depth = INFINITY;
  }
  
/*---------------------------------------------------------------------
* Round Control
*---------------------------------------------------------------------*/
  // Get next round