treeroutingenginep.nc

来自「tinyos-2.0源代码！转载而已！要的尽管拿！」· NC 代码 · 共 524 行 · 第 1/2 页

#include <Timer.h>
#include <TreeRouting.h>
#include <CollectionDebugMsg.h>
/* $Id: TreeRoutingEngineP.nc,v 1.1.2.18 2006/06/23 20:24:38 kasj78 Exp $ */
/*
 * "Copyright (c) 2005 The Regents of the University  of California.  
 * All rights reserved.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose, without fee, and without written agreement is
 * hereby granted, provided that the above copyright notice, the following
 * two paragraphs and the author appear in all copies of this software.
 * 
 * IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
 * OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
 * CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS."
 *
 */

/*
 *  @author Rodrigo Fonseca
 *  Acknowledgment: based on MintRoute, by Philip Buonadonna, Alec Woo, Terence Tong, Crossbow
 *                           MultiHopLQI
 *                           
 *  @date   $Date: 2006/06/23 20:24:38 $
 *  @see Net2-WG
 */

generic module TreeRoutingEngineP(uint8_t routingTableSize) {
    provides {
        interface UnicastNameFreeRouting as Routing;
        interface RootControl;
        interface TreeRoutingInspect;
        interface StdControl;
        interface Init;
    } 
    uses {
        interface AMSend as BeaconSend;
        interface Receive as BeaconReceive;
        interface LinkEstimator;
        interface AMPacket;
        interface LinkSrcPacket;
        interface SplitControl as RadioControl;
        interface Timer<TMilli> as BeaconTimer;
        interface Random;
        interface CollectionDebug;
    }
}


implementation {


    //No sense updating or sending beacons if radio is off
    bool radioOn = FALSE;
    //Start and stop control this. Stops updating and sending beacons
    bool running = FALSE;
    //Guards the beacon buffer
    bool sending = FALSE;
    //Tells updateNeighbor that the parent was just evicted
    bool justEvicted = FALSE;

    route_info_t routeInfo;
    bool state_is_root;
    am_addr_t my_ll_addr;

    message_t beaconMsgBuffer;
    beacon_msg_t* beaconMsg;

    /* routing table -- routing info about neighbors */
    routing_table_entry routingTable[routingTableSize];
    uint8_t routingTableActive;

    /* statistics */
    uint32_t parentChanges;
    /* end statistics */

    // forward declarations
    void routingTableInit();
    uint8_t routingTableFind(am_addr_t);
    error_t routingTableUpdateEntry(am_addr_t, am_addr_t , uint8_t, uint16_t);
    error_t routingTableEvict(am_addr_t neighbor);


    command error_t Init.init() {
        uint8_t maxLength;
        radioOn = FALSE;
        running = FALSE;
        parentChanges = 0;
        state_is_root = 0;
        routeInfoInit(&routeInfo);
        routingTableInit();
        my_ll_addr = call AMPacket.address();
        beaconMsg = call BeaconSend.getPayload(&beaconMsgBuffer);
        maxLength = call BeaconSend.maxPayloadLength();
        dbg("TreeRoutingCtl","TreeRouting initialized. (used payload:%d max payload:%d!\n", 
              sizeof(beaconMsg), maxLength);
        return SUCCESS;
    }

    command error_t StdControl.start() {
        //start will (re)start the sending of messages
        uint16_t nextInt;
        if (!running) {
            running = TRUE;
            nextInt = call Random.rand16() % BEACON_INTERVAL;
            nextInt += BEACON_INTERVAL >> 1;
            call BeaconTimer.startOneShot(nextInt);
            dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
        }     
        return SUCCESS;
    }

    command error_t StdControl.stop() {
        running = FALSE;
        dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
        return SUCCESS;
    } 

    event void RadioControl.startDone(error_t error) {
        radioOn = TRUE;
        dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
        if (running) {
            uint16_t nextInt;
            nextInt = call Random.rand16() % BEACON_INTERVAL;
            nextInt += BEACON_INTERVAL >> 1;
            call BeaconTimer.startOneShot(nextInt);
        }
    } 

    event void RadioControl.stopDone(error_t error) {
        radioOn = FALSE;
        dbg("TreeRoutingCtl","%s running: %d radioOn: %d\n", __FUNCTION__, running, radioOn);
    }

    /* Is this quality measure better than the minimum threshold? */
    // Implemented assuming quality is EETX
    bool passLinkMetricThreshold(uint16_t metric) {
        return (metric < ETX_THRESHOLD);
    }

    /* Converts the output of the link estimator to path metric
     * units, that can be *added* to form path metric measures */
    uint16_t evaluateMetric(uint8_t quality) {
        //dbg("TreeRouting","%s %d -> %d\n",__FUNCTION__,quality, quality+10);
        return (quality + 10);
    }

    /* updates the routing information, using the info that has been received
     * from neighbor beacons. Two things can cause this info to change: 
     * neighbor beacons, changes in link estimates, including neighbor eviction */
    task void updateRouteTask() {
        uint8_t i;
        routing_table_entry* entry;
        routing_table_entry* best;
        uint16_t minMetric;
        uint16_t currentMetric;
        uint16_t linkMetric, pathMetric;

        if (state_is_root)
            return;

        best = NULL;
        minMetric = MAX_METRIC;
        currentMetric = MAX_METRIC;

        dbg("TreeRouting","%s\n",__FUNCTION__);

         //find best path in table, other than our current
        for (i = 0; i < routingTableActive; i++) {
            entry = &routingTable[i];

            // Avoid bad entries and 1-hop loops
            if (entry->info.parent == INVALID_ADDR || entry->info.parent == my_ll_addr) {
              dbg("TreeRouting", "routingTable[%d]: neighbor: [id: %d parent: %d hopcount: %d metric: NO ROUTE]\n",  i, entry->neighbor, entry->info.parent, entry->info.hopcount);
              continue;
            }
            
            linkMetric = evaluateMetric(call LinkEstimator.getLinkQuality(entry->neighbor));
            dbg("TreeRouting", 
                "routingTable[%d]: neighbor: [id: %d parent: %d hopcount: %d metric: %d]\n",  
                i, entry->neighbor, entry->info.parent, 
                entry->info.hopcount, linkMetric);
            dbg_clear("TreeRouting", "   metric: %hu.\n", linkMetric);
            pathMetric = linkMetric + entry->info.metric;
            //for current parent
            if (entry->neighbor == routeInfo.parent) {
                dbg("TreeRouting", "   already parent.\n");
                currentMetric = pathMetric;
                //update routeInfo with parent's current info
                atomic {
                    routeInfo.metric = entry->info.metric;
                    routeInfo.hopcount = entry->info.hopcount + 1;
                }
                continue;
            }
            if (!passLinkMetricThreshold(linkMetric)) {
              dbg("TreeRouting", "   did not pass threshold.\n");
              continue;
            }
            
            if (pathMetric < minMetric) {
                minMetric = pathMetric;
                best = entry;
            }  
        }

        //now choose between current/best
        if (minMetric != MAX_METRIC) {
            if (currentMetric == MAX_METRIC ||
                minMetric + PARENT_SWITCH_THRESHOLD < currentMetric) {
                // routeInfo.metric will not store the composed metric.
                // since the linkMetric may change, we will compose whenever
                // we need it: i. when choosing a parent (here); 
                //            ii. when choosing a next hop
                parentChanges++;
                dbg("TreeRouting","Changed parent. from %d to %d\n", routeInfo.parent, best->neighbor);
                call CollectionDebug.logEventRoute(NET_C_TREE_NEW_PARENT, best->neighbor, best->info.hopcount + 1, best->info.metric); 
                call LinkEstimator.unpinNeighbor(routeInfo.parent);
                call LinkEstimator.pinNeighbor(best->neighbor);
                atomic {
                    routeInfo.parent = best->neighbor;
                    routeInfo.metric = best->info.metric;
                    routeInfo.hopcount = best->info.hopcount + 1; 
                }
            }
        }    

        //finally, tell people what happened
        if (justEvicted && routeInfo.parent == INVALID_ADDR) 
            signal Routing.noRoute();
        else if (!justEvicted && minMetric != MAX_METRIC)
            signal Routing.routeFound();
        justEvicted = FALSE; 
    }

    /* Inspection interface implementations */
    

    /* send a beacon advertising this node's routeInfo */
    // only posted if running and radioOn
    task void sendBeaconTask() {
        error_t eval;
        if (sending) {
            return;
        }
        beaconMsg->parent = routeInfo.parent;
        beaconMsg->hopcount = routeInfo.hopcount;

        if (state_is_root || routeInfo.parent == INVALID_ADDR) {
            beaconMsg->metric = routeInfo.metric;
        } else {
            beaconMsg->metric = routeInfo.metric +
                                evaluateMetric(call LinkEstimator.getLinkQuality(routeInfo.parent)); 
        }