/** * Jeff Rupp * Master's Thesis * 2005 * * Implementation of the HEED algorithm * "Distributed Clustering in Ad-hoc Sensor Networks: A Hybrid, Energy-Efficient Approach" * Ossama Younis and Sonia Famy, IEEE INFOCOM 2004 * * The HEED algorithm is similar is some respects to the JDR algorithm, the notable differences * are that it uses 1 level (of several) to denote cluster range, and it uses a probablity * formual similar to LEACH to change heads in a LEACH-like rounds system. The * difference from LEACH is that the cluster head selection takes into account the * current power reseves of the node * Note that in the case of multiple choices for cluster head a node chooses the head * that requires the lowest power * * Conversion from watts to dBm: * dBm = 10 log [Signal (mW)/1mW] * * 2 AA alkalines are worth about 4.5 watt-hours * http://www.powerstream.com/Compare.htm * watch batteries have approx. 10 joule 1 watt-hour == 3600 Joule., so 0.0028 watt-hour * */ package jdr.mobisim; import java.util.*; import org.apache.log4j.*; import jdr.utils.*; import java.awt.*; public class MobileNodeHeed implements EventCallbackIF, NodeIF { private static final boolean DO_LOADS_OF_LOGS = false; private static final boolean DO_SCHEDULER_LOGS = false; private static final boolean DO_PROCESS_PACKET_LOGS = false; private static final boolean DO_CLUSTER_FORM_LOGS = true; private static final boolean DO_SENSOR_DATA_LOGS = true; private static final boolean DO_MESSAGE_PROPAGATE_LOGS = true; private static Logger m_logger = Logger.getLogger(MobileNodeHeed.class); public EDU.oswego.cs.dl.util.concurrent.Mutex m_busyLock = new EDU.oswego.cs.dl.util.concurrent.Mutex(); public static final double MIN_TRANSMIT_POWER_DBM = -25.0; public static final double MAX_TRANSMIT_POWER_DBM = 10.0; private static final int s_ticsConsumedByHello = 5; private static final int s_ticsConsumedTellHead = 2; private static final int s_ticsConsumedRejectHead = 5; private static final int s_ticsConsumedByChooseHead = 15; private static final int s_ticsConsumedRecordHelloPacket = 2; private static final int s_ticsConsumedBySendData = 25; private static final int s_ticsConsumedByJoinCluster = 14; private static final int s_ticsConsumedByAdvertise = 25; private static final int s_RETRY_TRANSMIT_SLEEP_TICS = 35; private static final int s_ticsDelayBetweenTellFormOwnCluster = 500; // set a time at which we'll try to form our own cluster, > 0 means want to form private long m_whenToFormOwnCluster = -1; private double m_currentPowerdBm; // the location is used in sending data via the propagation model, so that it knows // where the message came from and thus what other nodes can hear it private FloatPoint m_location = new FloatPoint(0,0); private static int s_nodeCount = 0; private int m_myNodeNumber = 0; private boolean m_saidHello = false; private boolean m_amClustered = false; private double m_numNodesPerCluster = 10; // note that the power consumed is actually kept track in the protocol, since that // is where the transmits are taking place private double m_powerReserveWattHours = 4.5; // about how many watt-hours 2 AA alkalines are worth private double m_dataRateBps = 100000.0; private double m_maxPowerReserveWattHours = m_powerReserveWattHours; private double m_currentTransmitPowerLeveldBm = MAX_TRANSMIT_POWER_DBM; private double m_lastTransmitPowerLeveldBm = MIN_TRANSMIT_POWER_DBM; private double m_helloTransmitIncrement = MAX_TRANSMIT_POWER_DBM - MIN_TRANSMIT_POWER_DBM; private HashMap m_levelsToNodesHeardMap = new HashMap(); private long m_simTimeAtExecute = 0; private byte m_numberOfHelloTransmitLevels = 1; private double m_rehelloPercent = 0.6; private byte m_currentHelloTransmitLevel = 0; private boolean m_doingNormalComm = false; private long m_whenToSendSensorData = 0; private byte m_sensorDataSizeBytes = 10; private int m_sensorDataHeaderSizeBytes = 16; private int m_sensorDataTicsBetweenTransmits = 1000; private java.util.Random m_rand = new java.util.Random(12344123); private Vector m_nodesHeard = new Vector(); private Vector m_clusterMembers = new Vector(); private Vector m_rejectedHeadNodes = new Vector(); private java.lang.Object m_propagatedMessageNumbersLock = new java.lang.Object(); private Vector m_propagatedMessageNumbers = new Vector(); private ProtocolIF m_protocol = null; // flag to set if this node should highlite itself private boolean m_highlite = false; private boolean m_drawTransmitRings = false; private java.text.DecimalFormat m_percentFormat = new java.text.DecimalFormat("##.00"); private int m_ticsPassedDuringThisExecute = 0; // state of the node, determines what we do when ExecuteEvent is called private int m_nodeState = -1; private static final int SEND_HELLO_MESSAGE = 0; private static final int AWAITING_RTS = 10; private static final int AWAITING_CTS = 20; private static final int AWAITING_PACKET = 30; private static final int AWAITING_ACK = 40; private static final int SEND_SENSOR_DATA_MESSAGE = 50; private static final int SEND_CLUSTERED_DATA_MESSAGE = 60; private static final int SEND_CLUSTER_HEAD_GETTING_TIRED_MESSAGE = 70; private static final int TRANSMITTING = 80; // leach specific vars private double m_clusterHeadPercentage = 0.05; // fixed, but is what they used for testing private double m_minProbablity = 1/m_maxPowerReserveWattHours; private int m_roundNumber = 0; private long m_lastRoundTime = Integer.MIN_VALUE; private static final int s_timeBetweenRounds = 10000; private static final int s_longEnoughForOneIteration = 20; private int m_myClusterHead = -1; private boolean m_needToChooseHead = false; private double m_probabilityClusterHead = 0.0; private double m_clusterHeadTransmitLevelDbm = MAX_TRANSMIT_POWER_DBM; private Vector m_advertisedNodesHeard = new Vector(); /** * create a MobileNodeHeed, the first node created is the one to send the initial * Hello message */ public MobileNodeHeed() { m_myNodeNumber = s_nodeCount++; // get a unique instance of the ProtocolIF, one per node to handle the protocol m_protocol = ProtocolIF.getNewInstance(); m_protocol.setMyNodeNumber(m_myNodeNumber); m_protocol.setNodeEventCallbackIf(this); m_protocol.SetDataRate(m_dataRateBps); // start by saying 'hello' m_nodeState = SEND_HELLO_MESSAGE; Scheduler.getInstance().ScheduleEvent(this, DO_SCHEDULER_LOGS); } public static void ResetNodeCount() { s_nodeCount = 0; } public String GetAlgorithmName() { return "HEED Algorithm"; } /** * enqueue a packet to be processed, and schedule ourselves to process the packet * if we aren't busy with another packet already (Except if this packe is * a CTS or ACK, then we need to process it) * * @param packet the packet to enqueue */ public void ReceivePacket(PacketIF packet) { // determine if we are the destination for this packet int sourceNum = packet.extractInt(packet.getData(), MobilePacket.SOURCE_NODE_BYTE_OFFSET); //m_logger.debug("node: " + m_myNodeNumber + " received packet from node: "+sourceNum); if(sourceNum != m_myNodeNumber) { byte [] data = packet.getData(); int destNum = packet.extractInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET); if((destNum == -1) || (destNum == m_myNodeNumber)) { // packet is for us, enqueue and schedule ourselves to process it m_protocol.AddPacket(packet); } } } /** * do whatever we were waiting to be allowed to do * @return true if node isn't already occupied doing something else, * false if the node is already busy (will leave packet on sceduler queue) */ public boolean ExecuteEvent(long timeNow) { // If we're busy we return false and leave them on the queue and will process them when we've // finished what we are doing currently try { if(!m_busyLock.attempt(0)) { return false; } } catch(InterruptedException iex) { m_logger.error("node: "+m_myNodeNumber+" ExecuteEvent, state: "+GetNodeStateString(m_nodeState)+ " at time of: " + timeNow+" caught interrupted exc, returned false"); if(m_protocol.GetPacketQueueSize() > 0) { // request time from scheduler to deal with the next packet Scheduler.getInstance().ScheduleEvent(this, DO_SCHEDULER_LOGS); } m_busyLock.release(); return false; } m_ticsPassedDuringThisExecute = 0; m_simTimeAtExecute = timeNow; if(DO_LOADS_OF_LOGS) { m_logger.debug("node: "+m_myNodeNumber+" ExecuteEvent, state: "+GetNodeStateString(m_nodeState)+ " at time of: " + timeNow); } // note it is always OK to receive a packet in any of the states, // will have to determine what to do with it based on the node's state switch(m_nodeState) { case SEND_HELLO_MESSAGE: SendHello(); break; case AWAITING_RTS: break; case AWAITING_PACKET: break; case SEND_SENSOR_DATA_MESSAGE: m_whenToSendSensorData = timeNow; m_nodeState = AWAITING_RTS; break; case SEND_CLUSTERED_DATA_MESSAGE: SendClusterheadPackedData(); m_nodeState = AWAITING_RTS; break; case SEND_CLUSTER_HEAD_GETTING_TIRED_MESSAGE: m_nodeState = AWAITING_RTS; break; default: // we weren't expecting to do something in particular, so assume // somebody sent a packet break; } if(!m_saidHello) { SendHello(); } if(m_doingNormalComm && (timeNow >= (m_lastRoundTime + s_timeBetweenRounds))) { if(DO_CLUSTER_FORM_LOGS) { m_logger.debug("simTime: "+timeNow+ " New Cluster form round for node: " + m_myNodeNumber); } m_lastRoundTime = timeNow; // reset the probablity that this node will be a cluster head // CHprob = Cprob*(Eresidual/Emax) m_probabilityClusterHead = m_clusterHeadPercentage * GetRemainingPower() / m_maxPowerReserveWattHours; if(m_probabilityClusterHead < 0.0001) { // ensures the algorithm will finish m_probabilityClusterHead = 0.0001; } // clear out the other potential cluster heads heard synchronized(m_advertisedNodesHeard) { m_advertisedNodesHeard.removeAllElements(); } synchronized(m_clusterMembers) { m_clusterMembers.removeAllElements(); } m_myClusterHead = -1; m_clusterHeadTransmitLevelDbm = MAX_TRANSMIT_POWER_DBM; m_needToChooseHead = true; } if(m_needToChooseHead == true) { ChooseHead(timeNow); } // we'll always call ProcessPacket to ensure that we take care of our queue ProcessPacket(); // check if we're sending our periodic messages if(m_doingNormalComm && (timeNow >= m_whenToSendSensorData)) { SendSensorData(timeNow); } m_busyLock.release(); if(m_protocol.GetPacketQueueSize() > 0) { // request time from scheduler to deal with the next packet Scheduler.getInstance().ScheduleEvent(this, timeNow + m_ticsPassedDuringThisExecute, DO_SCHEDULER_LOGS); } return true; } private void SendHello() { if(GetRemainingPower() <= 0) { // use up some time just to keep the clock ticking Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, 5); return; } m_saidHello = true; PacketIF packet = PacketIF.getNewInstance(); if(packet != null) { // the hello is a broadcast, so no need to do the whole RTS/CTS/Send/ACK sequence byte [] data = new byte[MobilePacket.BEGIN_GENERIC_DATA_BYTE_OFFSET + 1 + PacketIF.CRC_SIZE_BYTES]; packet.setData(data); // don't care about sequence number when broadcasting packet.insertInt(data, MobilePacket.SEQUENCE_NUMBER_BYTE_OFFSET, -1); packet.insertInt(data, MobilePacket.ACK_SEQUENCE_NUMBER_BYTE_OFFSET, -1); packet.insertInt(data, MobilePacket.SOURCE_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET, -1); // no particular destination, anybody who hears packet.insertInt(data, MobilePacket.LAST_NODE_BYTE_OFFSET, -1); packet.insertInt(data, MobilePacket.NEXT_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.MESSAGE_NUMBER_BYTE_OFFSET, packet.GetNextMessageNumber()); data[MobilePacket.MESSAGE_TYPE_BYTE_OFFSET] = MobilePacket.HELLO_MESSAGE; data[MobilePacket.MESSAGE_LENGTH_BYTE_OFFSET] = 0; // one hello, at the selected re-hello percent point m_currentTransmitPowerLeveldBm = m_currentHelloTransmitLevel * m_helloTransmitIncrement; if(DO_LOADS_OF_LOGS) { m_logger.debug("node: "+m_myNodeNumber+" sending hello at power level: "+ m_currentHelloTransmitLevel+" which is: "+ m_currentTransmitPowerLeveldBm+" dBm"); } // consume a few tics to do our work Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, s_ticsConsumedByHello); m_ticsPassedDuringThisExecute += s_ticsConsumedByHello; PropagationIF prop = PropagationIF.getInstance(); if(prop != null) { double xmitWatts = (Math.pow(10.0, (m_currentTransmitPowerLeveldBm / 10))) / 1000; // next calculate what portion of an hour based on the packet size and // our data rate. xmitWatts *= (packet.getTransmitedBitCount() / m_dataRateBps) / ProtocolIF.s_SECONDS_PER_HOUR; // last thing to do to the packet before sending is insert the CRC PacketIF.AddCrc(data); int prevState = m_nodeState; m_nodeState = TRANSMITTING; m_lastTransmitPowerLeveldBm = m_currentTransmitPowerLeveldBm; prop.TransmitData(m_simTimeAtExecute + s_ticsConsumedByHello, data.length * 8, packet, m_location, m_currentTransmitPowerLeveldBm, DO_LOADS_OF_LOGS); packet.IncrementPowerConsumedInTransit(xmitWatts); m_powerReserveWattHours -= xmitWatts; } // one hello only m_nodeState = AWAITING_RTS; } } private void SendSensorData(long timeNow) { if(GetRemainingPower() <= 0) { // use up some time just to keep the clock ticking Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, 5); return; } // send sensor data // outside packet != null block for logging int sensorData = m_rand.nextInt(); PacketIF packet = PacketIF.getNewInstance(); if(packet != null) { // the hello is a broadcast, so no need to do the whole RTS/CTS/Send/ACK sequence byte [] data = new byte[MobilePacket.BEGIN_GENERIC_DATA_BYTE_OFFSET + m_sensorDataSizeBytes + m_sensorDataHeaderSizeBytes + PacketIF.CRC_SIZE_BYTES]; packet.setData(data); int seqNum = PacketIF.GetNextSequenceNumber(); packet.insertInt(data, MobilePacket.SEQUENCE_NUMBER_BYTE_OFFSET, seqNum); packet.insertInt(data, MobilePacket.ACK_SEQUENCE_NUMBER_BYTE_OFFSET, 0); packet.insertInt(data, MobilePacket.SOURCE_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.MESSAGE_NUMBER_BYTE_OFFSET, packet.GetNextMessageNumber()); int destNode = m_myClusterHead; double xmitPwr = m_clusterHeadTransmitLevelDbm; if(m_amClustered && (m_myClusterHead == m_myNodeNumber)) { // we're the cluster head, need to send summary message along ??? // for now the summary message is the same size as the normal message destNode = -1; xmitPwr = MAX_TRANSMIT_POWER_DBM; data[MobilePacket.MESSAGE_TYPE_BYTE_OFFSET] = MobilePacket.BETWEEN_CLUSTER; } else { xmitPwr = GetMinTransmitDbm(destNode); data[MobilePacket.MESSAGE_TYPE_BYTE_OFFSET] = MobilePacket.INSIDE_CLUSTER; } packet.insertInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET, destNode); packet.insertInt(data, MobilePacket.LAST_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.NEXT_NODE_BYTE_OFFSET, destNode); data[MobilePacket.MESSAGE_LENGTH_BYTE_OFFSET] = m_sensorDataSizeBytes; packet.insertInt(data, MobilePacket.BEGIN_GENERIC_DATA_BYTE_OFFSET + m_sensorDataHeaderSizeBytes, sensorData); // consume some tics for sending data Scheduler.getInstance().IncrementSimulationTics(timeNow, s_ticsConsumedBySendData); m_ticsPassedDuringThisExecute += s_ticsConsumedBySendData; boolean rc = false; rc = m_protocol.TransmitData(timeNow, data.length * 8, packet, m_location, xmitPwr, DO_LOADS_OF_LOGS); } // schedule for next periodic transmit m_whenToSendSensorData = timeNow + m_sensorDataTicsBetweenTransmits; if(DO_SENSOR_DATA_LOGS) { m_logger.debug("node: "+m_myNodeNumber+" sending periodic data: " + sensorData+ " at time: " + timeNow + " will send next at time: "+ m_whenToSendSensorData); } // schedule event at time in future for normal comm msg Scheduler.getInstance().ScheduleEvent(this, m_whenToSendSensorData, DO_SCHEDULER_LOGS); } private void SendClusterheadPackedData() { // ??? send sensor cluster head packed data } private void ProcessPacket() { if(DO_PROCESS_PACKET_LOGS) { m_logger.debug("ProcessPacket was called"); } PacketIF packet = m_protocol.PopNextPacket(); if(packet != null) { packet.setPacketArrived(); // ??? consume power to rcv packet if(GetRemainingPower() <= 0) { // use up some time just to keep the clock ticking Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, 5); return; } // ??? update statistics with data about this packet // get the data (the data is the only thing a real node would have available) byte [] data = packet.getData(); int sourceNode = MobilePacket.extractInt(data, MobilePacket.SOURCE_NODE_BYTE_OFFSET); int destinationNode = MobilePacket.extractInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET); int lastNode = MobilePacket.extractInt(data, MobilePacket.LAST_NODE_BYTE_OFFSET); int nextNode = MobilePacket.extractInt(data, MobilePacket.NEXT_NODE_BYTE_OFFSET); int ackNumber = MobilePacket.extractInt(data, MobilePacket.ACK_SEQUENCE_NUMBER_BYTE_OFFSET); int seqNumber = MobilePacket.extractInt(data, MobilePacket.SEQUENCE_NUMBER_BYTE_OFFSET); byte messageType = data[MobilePacket.MESSAGE_TYPE_BYTE_OFFSET]; byte messageLen = data[MobilePacket.MESSAGE_LENGTH_BYTE_OFFSET]; if(DO_PROCESS_PACKET_LOGS) { if((destinationNode == m_myNodeNumber) || (destinationNode == -1)) { m_logger.info("node: "+m_myNodeNumber+ " received a packet of type: "+ MobilePacket.GetMessageTypeString(messageType)+ " from node: " + sourceNode+ " seq num: "+seqNumber+ " ack num: "+ackNumber ); } } switch(messageType) { case MobilePacket.INSIDE_CLUSTER: if(m_myClusterHead == m_myNodeNumber) { // ??? cache the sensor data to be forwarded on during // the cluster head comm phase // for now we just ignore since the cluster head message is assumed // to be a summary, and the same size the other node data messages } break; case MobilePacket.BETWEEN_CLUSTER: if(m_myClusterHead == m_myNodeNumber) { // if we are a cluster head, then re-transmit the message PropagateMessage(packet); } break; case MobilePacket.HELLO_MESSAGE: { // record level PropagationIF prop = PropagationIF.getInstance(); NodeIF node = AllNodes.Instance().GetNodeByNumber(sourceNode); // since advertises occur at max power and the lowest power at which a signal // is received is -60 (see FreeAirPropagation for explanation), // the required transmit power is max - (minRcv - rcv) double lvl = packet.GetPacketTransmitPowerDbm() - (prop.GetReceiveSignalStrengthDbm(node.getLocation(), m_location, packet.GetPacketTransmitPowerDbm()) - (-60)); synchronized(m_nodesHeard) { m_nodesHeard.addElement(new HeedNodeHeard(sourceNode, lvl)); } break; } case MobilePacket.CHOOSE_HEADS: m_nodeState = AWAITING_RTS; break; case MobilePacket.TELL_HEAD: break; case MobilePacket.REJECT_HEAD: break; case MobilePacket.RTS: case MobilePacket.CTS: case MobilePacket.ACK: m_logger.warn("Node got message that should have been handled by the protocol layer"); break; case MobilePacket.OK_TO_DO_NORMAL_COMM: { // set flag so that we begin our 'normal comm' routine m_doingNormalComm = true; m_whenToSendSensorData = Scheduler.getInstance().GetSimulationTime() + m_sensorDataTicsBetweenTransmits; // schedule event at time in future for normal comm msg Scheduler.getInstance().ScheduleEvent(this, m_whenToSendSensorData, DO_SCHEDULER_LOGS); // propagate the OK_TO_DO_NORMAL_COMM message PropagateMessage(packet); m_nodeState = AWAITING_RTS; break; } case MobilePacket.OVERRIDE_HEAD: break; case MobilePacket.JOIN_CLUSTER: { // allow the other node to join if we are a clusterhead, or if we // had selected the node that is joining as our cluster head if((m_myClusterHead == m_myNodeNumber) || (sourceNode == m_myClusterHead)) { if(sourceNode == m_myClusterHead) { m_myClusterHead = m_myNodeNumber; m_clusterHeadTransmitLevelDbm = MAX_TRANSMIT_POWER_DBM; } m_logger.debug("node: "+sourceNode+" joined cluster of node: "+m_myNodeNumber); // find this node in our list of nodes heard HeedNodeHeard newNode = new HeedNodeHeard(sourceNode, GetMinTransmitLevel(sourceNode)); synchronized(m_clusterMembers) { m_clusterMembers.addElement(newNode); } } break; } case MobilePacket.LEACH_ADVERTISEMENT: { // record level PropagationIF prop = PropagationIF.getInstance(); NodeIF node = AllNodes.Instance().GetNodeByNumber(sourceNode); // since advertises occur at max power and the lowest power at which a signal // is received is -60 (see FreeAirPropagation for explanation), // the required transmit power is max - (minRcv - rcv) double lvl = packet.GetPacketTransmitPowerDbm() - (prop.GetReceiveSignalStrengthDbm(node.getLocation(), m_location, packet.GetPacketTransmitPowerDbm()) - (-60)); synchronized(m_advertisedNodesHeard) { m_advertisedNodesHeard.addElement(new HeedNodeHeard(sourceNode, lvl)); } break; } default: m_logger.warn("received a packet with an unknown type: "+ messageType); } } else { if(DO_PROCESS_PACKET_LOGS) { m_logger.error("ProcessPacket called, but no packets on queue"); } } } /** * decide if we should advertise to be a cluster head, if so send appropriate packet * after sending packet (or not sending) schedule ourselves to check advertisements at * a suitable future time when all possible advertisements have taken place */ protected void Advertise(long timeNow) { if(GetRemainingPower() <= 0) { // use up some time just to keep the clock ticking Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, 5); return; } // schedule the next round Scheduler.getInstance().ScheduleEvent(this, m_lastRoundTime + s_timeBetweenRounds, DO_SCHEDULER_LOGS); m_myClusterHead = m_myNodeNumber; m_clusterHeadTransmitLevelDbm = MAX_TRANSMIT_POWER_DBM; m_needToChooseHead = false; PacketIF packet = PacketIF.getNewInstance(); if(packet != null) { // the hello is a broadcast, so no need to do the whole RTS/CTS/Send/ACK sequence byte [] data = new byte[MobilePacket.BEGIN_GENERIC_DATA_BYTE_OFFSET + PacketIF.CRC_SIZE_BYTES]; packet.setData(data); int seqNum = PacketIF.GetNextSequenceNumber(); packet.insertInt(data, MobilePacket.SEQUENCE_NUMBER_BYTE_OFFSET, seqNum); packet.insertInt(data, MobilePacket.ACK_SEQUENCE_NUMBER_BYTE_OFFSET, 0); packet.insertInt(data, MobilePacket.SOURCE_NODE_BYTE_OFFSET, m_myNodeNumber); int destNode = -1; double xmitPwr = MAX_TRANSMIT_POWER_DBM; data[MobilePacket.MESSAGE_TYPE_BYTE_OFFSET] = MobilePacket.LEACH_ADVERTISEMENT; packet.insertInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET, destNode); packet.insertInt(data, MobilePacket.LAST_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.NEXT_NODE_BYTE_OFFSET, destNode); packet.insertInt(data, MobilePacket.MESSAGE_NUMBER_BYTE_OFFSET, packet.GetNextMessageNumber()); data[MobilePacket.MESSAGE_LENGTH_BYTE_OFFSET] = 0; // consume some tics for sending data Scheduler.getInstance().IncrementSimulationTics(timeNow, s_ticsConsumedByAdvertise); m_ticsPassedDuringThisExecute += s_ticsConsumedByAdvertise; boolean rc = false; rc = m_protocol.TransmitData(timeNow, data.length * 8, packet, m_location, xmitPwr, DO_LOADS_OF_LOGS); } } /** * Find a cluster head, note that this is an iterative process for HEED, * with the probability that this node will be a head doubling each round */ protected void ChooseHead(long timeNow) { if(!m_needToChooseHead) { // we're already clustered return; } SetHighliteClusterMembers(false, m_myClusterHead); // determine if we should advertise to be a cluster head based on HEED algorithm: // CHprob = Cprob*(Eresidual/Emax) double lowestLevel = MAX_TRANSMIT_POWER_DBM; int clusterHead = -1; int numHeard = 0; synchronized(m_advertisedNodesHeard) { numHeard = m_advertisedNodesHeard.size(); Iterator iter = m_advertisedNodesHeard.iterator(); while(iter.hasNext()) { HeedNodeHeard node = (HeedNodeHeard)iter.next(); if(node.m_levelHeard < lowestLevel) { clusterHead = node.m_nodeNumber; lowestLevel = node.m_levelHeard; } } } // heard no other nodes, see if we want to be a cluster head if(clusterHead == -1) { if(m_probabilityClusterHead >= 1) { // become a clusterhead ourselves if(DO_CLUSTER_FORM_LOGS) { m_logger.debug("simTime: "+timeNow+ " node: "+m_myNodeNumber+ " becoming a cluster head"); } Advertise(timeNow); } else { if(DO_CLUSTER_FORM_LOGS) { m_logger.debug("simTime: "+timeNow+ " node: "+m_myNodeNumber+ " failed to find a cluster head"+ " probability of my becoming a cluster head: " + m_probabilityClusterHead+ " waiting for "+s_longEnoughForOneIteration+" tics to check again"); } m_needToChooseHead = true; m_probabilityClusterHead *= 2; // schedule ourselves to check for other cluster heads in a little bit Scheduler.getInstance().ScheduleEvent(this, timeNow + s_longEnoughForOneIteration, DO_SCHEDULER_LOGS); } } else { m_needToChooseHead = false; m_myClusterHead = clusterHead; m_clusterHeadTransmitLevelDbm = lowestLevel; // join cluster for the head we heard JoinOtherCluster(); if(DO_CLUSTER_FORM_LOGS) { m_logger.debug("node: "+m_myNodeNumber+" Choose cluster head as node: "+m_myClusterHead+ " from list of nodes heard of length: " + numHeard + " with level: "+lowestLevel); } // schedule the next round Scheduler.getInstance().ScheduleEvent(this, m_lastRoundTime + s_timeBetweenRounds, DO_SCHEDULER_LOGS); } Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, s_ticsConsumedByChooseHead); m_ticsPassedDuringThisExecute += s_ticsConsumedByChooseHead; } protected void JoinOtherCluster() { PacketIF packet = PacketIF.getNewInstance(); byte [] data = new byte[MobilePacket.BEGIN_GENERIC_DATA_BYTE_OFFSET + PacketIF.CRC_SIZE_BYTES]; packet.setData(data); int seqNum = PacketIF.GetNextSequenceNumber(); packet.insertInt(data, MobilePacket.SEQUENCE_NUMBER_BYTE_OFFSET, seqNum); packet.insertInt(data, MobilePacket.ACK_SEQUENCE_NUMBER_BYTE_OFFSET, 0); packet.insertInt(data, MobilePacket.SOURCE_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET, m_myClusterHead); packet.insertInt(data, MobilePacket.LAST_NODE_BYTE_OFFSET, m_myNodeNumber); packet.insertInt(data, MobilePacket.NEXT_NODE_BYTE_OFFSET, m_myClusterHead); packet.insertInt(data, MobilePacket.MESSAGE_NUMBER_BYTE_OFFSET, packet.GetNextMessageNumber()); data[MobilePacket.MESSAGE_LENGTH_BYTE_OFFSET] = 0; data[MobilePacket.MESSAGE_TYPE_BYTE_OFFSET] = MobilePacket.JOIN_CLUSTER; double xmitPwr = GetMinTransmitDbm(m_myClusterHead); // last thing to do to the packet before sending is insert the CRC PacketIF.AddCrc(data); int prevState = m_nodeState; m_nodeState = TRANSMITTING; m_lastTransmitPowerLeveldBm = xmitPwr; boolean rc = false; rc = m_protocol.TransmitData(m_simTimeAtExecute + s_ticsConsumedByJoinCluster, data.length * 8, packet, m_location, xmitPwr, DO_LOADS_OF_LOGS); m_nodeState = prevState; // consume a few tics to do our work Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, s_ticsConsumedByJoinCluster); m_ticsPassedDuringThisExecute += s_ticsConsumedByJoinCluster; } /** * propagates a packet by sending it out again at a broadcast level appropriate to the * destination node (if this node didn't hear the node then send message at max power */ protected void PropagateMessage(PacketIF packet) { if(GetRemainingPower() <= 0) { // use up some time just to keep the clock ticking Scheduler.getInstance().IncrementSimulationTics(m_simTimeAtExecute, 5); return; } byte [] data = packet.getData(); int sourceNode = MobilePacket.extractInt(data, MobilePacket.SOURCE_NODE_BYTE_OFFSET); int destinationNode = MobilePacket.extractInt(data, MobilePacket.DESTINATION_NODE_BYTE_OFFSET); int msgNumber = MobilePacket.extractInt(data, MobilePacket.MESSAGE_NUMBER_BYTE_OFFSET); // check the sequence number to see if we've forwarded this message before Integer newInteger = new Integer(msgNumber); synchronized(m_propagatedMessageNumbersLock) { if(m_propagatedMessageNumbers.contains(newInteger)) { // already propagated this message, just return return; } else { // add to the list of propagated sequence numbers m_propagatedMessageNumbers.addElement(newInteger); } } // increment the hop count packet.IncrementHopCount(1); double xmitPwr = GetMinTransmitDbm(destinationNode); long timeNow = Scheduler.getInstance().GetSimulationTime(); boolean rc; if(DO_MESSAGE_PROPAGATE_LOGS) { m_logger.debug("propagating packet: "+ packet.toString()); } // propagate the message rc = m_protocol.TransmitData(timeNow, data.length * 8, packet, m_location, xmitPwr); } protected double GetMinTransmitDbm(int destNode) { return GetMinTransmitLevel(destNode); } protected double GetMinTransmitLevel(int destNode) { double xmitLevel = MAX_TRANSMIT_POWER_DBM; // determine the transmit level needed to communicate with the // node we want to communicate with synchronized(m_nodesHeard) { int numHrd = m_nodesHeard.size(); for(int i = 0; i < numHrd; ++i) { HeedNodeHeard testHrd = ((HeedNodeHeard)m_nodesHeard.get(i)); if(testHrd.m_nodeNumber == destNode) { xmitLevel = testHrd.m_levelHeard; break; } } } if(DO_LOADS_OF_LOGS) { m_logger.debug("node: " + m_myNodeNumber +" heard node: "+destNode + " at level: "+xmitLevel); } return xmitLevel; } public void setNumberOfHelloTransmitLevels(byte numLevels) { m_numberOfHelloTransmitLevels = numLevels; if(numLevels > 1) { m_currentTransmitPowerLeveldBm = MIN_TRANSMIT_POWER_DBM; m_helloTransmitIncrement = (MAX_TRANSMIT_POWER_DBM - MIN_TRANSMIT_POWER_DBM) / (numLevels-1); m_currentHelloTransmitLevel = (byte)(m_numberOfHelloTransmitLevels * (1-m_rehelloPercent)); m_logger.debug("node: "+m_myNodeNumber+" number of transmit levels: "+numLevels+ " hello xmit level: "+m_currentHelloTransmitLevel+ " rehelloPercent: "+ m_rehelloPercent); } else { m_helloTransmitIncrement = MobileNodeHeed.MAX_TRANSMIT_POWER_DBM - MobileNodeHeed.MIN_TRANSMIT_POWER_DBM; } } /** * determines how many nodes will execute the hello sequence * as a percentage of the total number of transmit levels (e.g. 30% of 10 levels * means that the 3 highest power levels will execute the hello sequence) * Note that the 0..100.0 percentage is converted to 0..1.0 * * @param percentRehello (0..100.0) the percentage of total levels which will do the hello */ public void setRehelloPercent(double percentRehello) { m_rehelloPercent = percentRehello / 100.0; m_currentHelloTransmitLevel = (byte)(m_numberOfHelloTransmitLevels * (1-m_rehelloPercent)); m_logger.debug("node: "+m_myNodeNumber+" hello xmit level: "+m_currentHelloTransmitLevel+ " rehelloPercent: "+m_rehelloPercent); } public double GetRemainingPower() { return m_powerReserveWattHours - m_protocol.GetWattsConsumed(); } public double GetMaxPower() { return m_maxPowerReserveWattHours; } public void SetWattHours(double wattHours) { m_powerReserveWattHours = wattHours; m_maxPowerReserveWattHours = m_powerReserveWattHours; m_minProbablity = 1/m_maxPowerReserveWattHours; } public void setSensorDataSizeBytes(int numBytes) { m_sensorDataSizeBytes = (byte)numBytes; } public void setSensorDataHeaderSizeBytes(int numBytes) { m_sensorDataHeaderSizeBytes = numBytes; } public void setSensorDataTicsBetweenTransmits(int ticsBetweenTransmits) { m_sensorDataTicsBetweenTransmits = ticsBetweenTransmits; } /** * To avoid losing track of the location, only the AllNodes should call this * @param pt new location */ public void setLocation(jdr.utils.FloatPoint pt) { m_location = pt; m_protocol.setMyNodeLocation(m_location); } public jdr.utils.FloatPoint getLocation() { return m_location; } public int getNodeNumber() { return m_myNodeNumber; } public void SetNumNodesPerCluster(double nodesPerCluster) { m_numNodesPerCluster = nodesPerCluster; } public void SetDataRate(double dataRateBps) { m_dataRateBps = dataRateBps; m_protocol.SetDataRate(m_dataRateBps); } public PacketIF GetNextPacket() { return m_protocol.PeekNextPacket(); } public void SetHighliteCluster(boolean highlite) { SetHighliteCluster(highlite, true); } public void SetHighliteCluster(boolean highlite, boolean propagate) { if(m_highlite == highlite) { return; } if(!propagate) { return; } m_highlite = highlite; // pass message along to AllNodes, to get all cluster members highlited if(m_myClusterHead != -1) { AllNodes.Instance().HighlightCluster(m_myClusterHead, highlite); } } public void SetHighliteClusterMembers(boolean highlite, int clusterHead) { if(m_myClusterHead == clusterHead) { SetHighliteCluster(highlite, false); } } public void SetTransmitRingsOn(boolean ringsOn) { m_drawTransmitRings = ringsOn; } public void Draw(Graphics2D graphics, Rectangle bounds, double xScale, double yScale) { // draw the node, always show cluster heads in a different color Color origColor = graphics.getColor(); Color nodeStateColor = Color.red; switch(m_nodeState) { case SEND_HELLO_MESSAGE: nodeStateColor = Color.white; break; case AWAITING_RTS: nodeStateColor = Color.green; break; case AWAITING_CTS: nodeStateColor = Color.magenta; break; case AWAITING_PACKET: nodeStateColor = Color.blue; break; case AWAITING_ACK: nodeStateColor = Color.pink; break; case SEND_SENSOR_DATA_MESSAGE: nodeStateColor = Color.lightGray; break; case SEND_CLUSTERED_DATA_MESSAGE: nodeStateColor = Color.gray; break; case SEND_CLUSTER_HEAD_GETTING_TIRED_MESSAGE: nodeStateColor = Color.orange; break; case TRANSMITTING: nodeStateColor = Color.yellow; break; default: nodeStateColor = Color.red; break; } graphics.setColor(nodeStateColor); graphics.fillOval((int)(m_location.getX() / xScale), (int)(m_location.getY() / yScale), 6, 6); if(m_myClusterHead == m_myNodeNumber) { graphics.setColor(Color.cyan); graphics.fillRect((int)(m_location.getX() / xScale) -2, (int)(m_location.getY() / yScale) -2, 4, 4); } // if the m_highlite flag is set, add a circle around cluster-mates if(m_highlite) { graphics.setColor(Color.white); graphics.drawOval((int)(m_location.getX() / xScale) - 3, (int)(m_location.getY() / yScale) - 3, 12, 12); //m_logger.debug("Highliting node num: "+m_myNodeNumber); } if(m_drawTransmitRings) { graphics.setColor(Color.yellow); Stroke currentStroke = graphics.getStroke(); float [] dashInfo = new float[2]; dashInfo[0] = (float)2.0; dashInfo[1] = (float)4.0; graphics.setStroke(new BasicStroke((float)1.0, BasicStroke.CAP_SQUARE, BasicStroke.JOIN_ROUND, (float)1.0, dashInfo, (float)1.0)); PropagationIF propagation = PropagationIF.getInstance(); for(double pwr = MIN_TRANSMIT_POWER_DBM; pwr <= MAX_TRANSMIT_POWER_DBM; pwr += m_helloTransmitIncrement) { double distAtPwr = propagation.GetTransmitDistance(pwr); graphics.drawOval((int)((m_location.getX() / xScale) - ((distAtPwr / xScale) - 3)), (int)((m_location.getY() / yScale) - ((distAtPwr / yScale) - 3)), (int)(((distAtPwr / xScale) * 2)), (int)(((distAtPwr / yScale) * 2))); } graphics.setStroke(currentStroke); } // draw a circle representing the transmit distance if(m_nodeState == TRANSMITTING) { // get the propagation model so we can get the transmit distance PropagationIF propagation = PropagationIF.getInstance(); double distAtPwr = propagation.GetTransmitDistance(m_lastTransmitPowerLeveldBm); graphics.setColor(Color.yellow); Stroke currentStroke = graphics.getStroke(); float [] dashInfo = new float[2]; dashInfo[0] = (float)2.0; dashInfo[1] = (float)4.0; graphics.setStroke(new BasicStroke((float)1.0, BasicStroke.CAP_SQUARE, BasicStroke.JOIN_ROUND, (float)1.0, dashInfo, (float)1.0)); graphics.drawOval((int)((m_location.getX() / xScale) - ((distAtPwr / xScale) - 3)), (int)((m_location.getY() / yScale) - ((distAtPwr / yScale) - 3)), (int)(((distAtPwr / xScale) * 2)), (int)(((distAtPwr / yScale) * 2))); graphics.setStroke(currentStroke); } // draw the 'fuel guage' bar double powerReserve = m_powerReserveWattHours - m_protocol.GetWattsConsumed(); int guageAngle = (int)(-180 * (powerReserve / m_maxPowerReserveWattHours)); if(Math.abs(guageAngle) < 15) { guageAngle = -15; // enough to stay slightly visible } if(powerReserve <= 0) { guageAngle = -180; // all magenta indicates dead graphics.setColor(Color.magenta); } else if(powerReserve <= (m_maxPowerReserveWattHours / 10)) { graphics.setColor(Color.red); } else if(powerReserve < (m_maxPowerReserveWattHours / 2)) { graphics.setColor(Color.yellow); } else { graphics.setColor(Color.green); } graphics.fillArc((int)(m_location.getX() / xScale) + 6, (int)(m_location.getY() / yScale) + 6, 10, 10, 180, guageAngle); graphics.setColor(origColor); m_protocol.Draw(graphics, bounds, xScale, yScale); } public String toString() { return "MobileNodeHeed node: " + m_myNodeNumber; } /** * dumps the nodes this node has heard during the 'hello' sequence to the logger */ public void DumpNodesHeard() { String nodesHrd = ""; synchronized(m_nodesHeard) { int numNodes = m_nodesHeard.size(); for(int i = 0; i < numNodes; ++i) { nodesHrd += " " + m_nodesHeard.get(i).toString() + "\n"; } if(numNodes == 0) { nodesHrd += " None\n"; } } m_logger.debug("Nodes heard by node: " + m_myNodeNumber + " total ("+m_nodesHeard.size()+")" + " :\n" + nodesHrd); } public void DumpNodePacketQueue() { int numPacketsInQueue = 0; boolean busy = true; try { busy = !(m_busyLock.attempt(1)); if(!busy) { // we weren't busy, so release the mutex m_busyLock.release(); } } catch(InterruptedException ie) { busy = false; } String logStr = "node: "+m_myNodeNumber+ " busy status: "+ busy + " node state: "+GetNodeStateString(m_nodeState); logStr += m_protocol.DumpPacketQueue(); m_logger.debug(logStr); } /** * dumps the cluster information: * who is head for this node, or if this node is a head, the nodes it is * head for */ public void DumpClusterInfo() { String msg = GetClusterInfo(); m_logger.debug(msg); } public String GetClusterInfo() { String msg = ""; if(m_myClusterHead == m_myNodeNumber) { String clusterMembers = ""; synchronized(m_clusterMembers) { int numNodes = m_clusterMembers.size(); for(int i = 0; i < numNodes; ++i) { clusterMembers += " " + m_clusterMembers.get(i).toString() + "\n"; } if(numNodes == 0) { clusterMembers += " None\n"; } } msg = "Cluster head node: "+ m_myNodeNumber + "\n Cluster members " + " total ("+m_clusterMembers.size()+")" + " :\n" + clusterMembers; } else { msg = "This node: "+ m_myNodeNumber + " has cluster head: "+ m_myClusterHead; } msg = msg + " highlite set to: "+m_highlite; msg = msg + " \r\n location of this node: "+m_location.toString(); double pwrRes = m_powerReserveWattHours - m_protocol.GetWattsConsumed(); msg = msg + "\r\n Power reserve Watts: " + pwrRes + " ("+m_percentFormat.format(100*(pwrRes / m_maxPowerReserveWattHours))+"%)"; return msg; } public String GetNodeStateString() { return GetNodeStateString(m_nodeState); } public String GetNodeStateString(int state) { String stateStr = "unknown"; switch(state) { case SEND_HELLO_MESSAGE: stateStr = "SEND_HELLO_MESSAGE"; break; case AWAITING_RTS: stateStr = "AWAITING_RTS"; break; case AWAITING_CTS: stateStr = "AWAITING_CTS"; break; case AWAITING_PACKET: stateStr = "AWAITING_PACKET"; break; case AWAITING_ACK: stateStr = "AWAITING_ACK"; break; case SEND_SENSOR_DATA_MESSAGE: stateStr = "SEND_SENSOR_DATA_MESSAGE"; break; case SEND_CLUSTERED_DATA_MESSAGE: stateStr = "SEND_CLUSTERED_DATA_MESSAGE"; break; case SEND_CLUSTER_HEAD_GETTING_TIRED_MESSAGE: stateStr = "SEND_CLUSTER_HEAD_GETTING_TIRED_MESSAGE"; break; case TRANSMITTING: stateStr = "TRANSMITTING"; break; default: break; } return stateStr; } //================================================================== // inner classes //================================================================== private class HeedNodeHeard { public int m_nodeNumber = -1; public double m_levelHeard = -1; public HeedNodeHeard() { } public HeedNodeHeard(int node, double lvl) { m_nodeNumber = node; m_levelHeard = lvl; } public boolean equals(Object obj) { boolean rc = false; if(obj instanceof NodeHeard) { rc = (((NodeHeard)obj).m_nodeNumber == m_nodeNumber); } return rc; } public String toString() { return "Node: " + m_nodeNumber + " level: " + m_levelHeard; } } } // end class definition