networkc.nc

用于传感器网络的节点操作系统 TinyOS 结构设计非常有意思

/*									tab:4
 *
 *
 * "Copyright (c) 2000-2002 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."
 *
 */
/*									tab:4
 *  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.  By
 *  downloading, copying, installing or using the software you agree to
 *  this license.  If you do not agree to this license, do not download,
 *  install, copy or use the software.
 *
 *  Intel Open Source License 
 *
 *  Copyright (c) 2002 Intel Corporation 
 *  All rights reserved. 
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions are
 *  met:
 * 
 *	Redistributions of source code must retain the above copyright
 *  notice, this list of conditions and the following disclaimer.
 *	Redistributions in binary form must reproduce the above copyright
 *  notice, this list of conditions and the following disclaimer in the
 *  documentation and/or other materials provided with the distribution.
 *      Neither the name of the Intel Corporation nor the names of its
 *  contributors may be used to endorse or promote products derived from
 *  this software without specific prior written permission.
 *  
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 *  PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE INTEL OR ITS
 *  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 *  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 *  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 *  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 *  LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 *  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 *  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 * 
 */
/*
 * Authors:	Sam Madden
 *              Design by Sam Madden, Wei Hong, and Joe Hellerstein
 * Date last modified:  6/26/02
 *
 *
 */


/* Routing component for TinyDB.  Can receive and send
   data and query messages.  Data messages are tuples
   or aggregate values.  Queries represent portions
   of queries being injected into the network.

   In the TAG world, query messages flood down the routing tree,
   and data messages are sent up the network (to the node's) parent
   towards the root.  Obviously, there are other routing mechanisms
   that might make sense,  but the routing system needs to be careful
   to do duplicate elimination -- which may be hard since this API
   doesn't export the contents of the data messages.

   Note that the send routines in this component depend on the higher
   level tuple router in several ugly ways:

   1) They expect that the TOS_MsgPtr's deliver have space for
   the appropriate TINYDB_NETWORK header (type DbMsgHdr) at the
   top.

   The basic routing algorithm implemented by this component works as follows:
   
   1) Each mote maintains a small buffer of "neighbor" motes it can hear
   2) For each neighbor, the mote tracks the signal quality by observing sequence
   numbers on messages from that neighbor degrading quality when messages are missed
   3) Each mote picks a parent from its neighbors;  ideally, parents will be
   motes that have a high signal quality and are close to the root
   4) Once a parent has been selected, motes stick to that parent unless the quality of
   the parent degrades substantially (even if another parent that is closer to the
   root with similar quality appears) -- this "topology stability" property is
   important for insuring correct computation of aggregates.

   These data structures have been updated to be parameterized by ROOT_ID, which allows us
   maintain several routing trees.  Note that we keep only one neighbor list
   (and estimate of quality per neighbor), but that we keep multiple levels for 
   each neighbor, ourself, and our parents.

   Authors:  Sam Madden -- basic structure, current maintainer
             Joe Hellerstein -- initial implementation of neighbor tracking and parent selection
*/



module NetworkC {

  provides {
    interface Network;
    interface StdControl;

  }

  uses {
    interface SendMsg as SendDataMsg;
    interface SendMsg as SendQueryMsg;
    interface SendMsg as SendQueryRequest;
    interface SendMsg as DebugMsg;
    interface SendMsg as SchemaMsg;

    interface ReceiveMsg as RcvDataMsg;
    interface ReceiveMsg as RcvQueryMsg;
    interface ReceiveMsg as RcvRequestMsg;
    interface ReceiveMsg as RcvSchemaMsg;

    interface CommandUse;
    interface Leds;
    interface Random;
    interface AttrRegister as ParentAttr;

    interface QueryProcessor;
  }
      
}

implementation {
  enum {
    LEVEL_UNKNOWN = -1,
    PARENT_UNKNOWN = -1,
    BAD_IX = -1,
    UNKNOWN_ROOT = -1,
    PARENT_RESELECT_INTERVAL = 5, //5 epochs
    PARENT_LOST_INTERVAL = 10, //5 epochs
    TIME_OF_FLIGHT = 0,
    NUM_RELATIVES = 5,
    MAX_PROB_THRESH = 127,  //only switch parents if there's a node thats a lot more reliable
    ALPHABITS = 2, // We do a moving average at time t where
                  // avg_t = avg_{t-1}*(1-alpha) + alpha*newvalue
                  // Since we're using integers, we shift by ALPHABITS, rather than multiplying
                  // by a fraction.
                  // so ALPHABITS=2 is like alpha = 0.25 (i.e. divide by 4)
    NACKALPHA= 4, //alpha bits to use on a failed ack
    QUERY_RETRIES = 5,
    NUM_ROOTS = 4,
    DATA_RETRIES = 0 //don't retry data messages for now, since we have no way of eliminating duplicates
  };


  uint16_t mSendCount; // increment each epoch
  // We track NUM_RELATIVES parents potential parents.
  // For each, we will track the mean # of drops of msgs from that "relative".
  char mRelatives[NUM_RELATIVES]; // an array of senders we're tracking potential parents
  char mRelOccupiedBits; // occupancy bitmap for slots in the relatives array
  short mParentIx[NUM_ROOTS]; // the current parent's index in the "relatives" array
                  // invariant: parentIx < NUM_RELATIVES
                  // invariant: relOccupiedBits is on for parentIx
  unsigned short mLastIdxRelative[NUM_RELATIVES]; // last idx # from this rel
  unsigned char mCommProb[NUM_RELATIVES]; // an 8-bit weighted moving average of
                                         // delivery success (delivered = 255,
                                         // dropped = 0).
  short mRoots[NUM_ROOTS];
  char mRelLevel[NUM_ROOTS][NUM_RELATIVES];  // current level of rel

  TOS_MsgPtr mMsg;
  TOS_Msg mDbg;
  char mAmId;
  uint8_t mIdx;
  bool mIsRoot;
  bool mForceTopology;
  bool mUart;  //is uart in use?
  bool mLocal; //was this message send local, or do our children need to see completion events
  bool mWasCommand; //is there a command that needs to be executed in dbg?
  bool mRadio; //is radio in use? (pending flag for radio)

  char mFanout;	// fanout of routing tree if forceTopology is true
  bool mCentralized; //all messages should be routed to the root (no aggregation?)
  short mMinparent; // min parent id number when we force topology
  short mMaxparent; // max parent id number when we force topology
  short mParentCand1, mParentCand2, mParentCand3;
  short mLastCheck, mLastHeard;


  enum {
    NUM_RECENT_MSGS = 8
  };

  long mRecentMsgs[NUM_RECENT_MSGS];
  uint8_t mNextMsg;

  short mRetryCnt;
  SchemaErrorNo errorNo;

  typedef enum {
    QUERY_TYPE = 0, 
    DATA_TYPE = 1
  } MsgType;

  typedef struct {
    short nodeid;
    short msgcount;
  } NodeMsgCount;

  typedef struct{
    DbMsgHdr hdr;
    char data[1];
  } NetworkMessage;


  void initHeader(DbMsgHdr *header,bool amRoot, uint8_t rootId);
  bool processHeader(DbMsgHdr header, MsgType type,uint8_t rootId);
  void setParentRange();
  void setRoot(uint8_t rootId);
  bool checkRoot(TOS_MsgPtr msg, uint8_t *rootId);
  void degradeLinkQuality(short neighborId);

  uint8_t myLevel(uint8_t rootId) {
    if (mRoots[rootId] == TOS_LOCAL_ADDRESS) return 0;
    if (mParentIx[rootId] == PARENT_UNKNOWN || mRelLevel[rootId][mParentIx[rootId]] == LEVEL_UNKNOWN)
      return LEVEL_UNKNOWN;
    return mRelLevel[rootId][mParentIx[rootId]] + 1;
  }

    command result_t StdControl.init() {
      int i;

      mSendCount = 0;
      mLastCheck = 0;
      mLastHeard = 0;

      mNextMsg = 0;
      for (i = 0; i < NUM_RECENT_MSGS; i++)
	mRecentMsgs[i] = 0xFFFFFFFF;

      // mark statistics invalid
      mRelOccupiedBits = 0;
      for (i = 0; i < NUM_ROOTS; i++) {
	mParentIx[i] = PARENT_UNKNOWN;
	mRoots[i] = UNKNOWN_ROOT;
      }

      mIdx = 0;
      mFanout = 0xFF; //default -- no fanout
      mCentralized = FALSE;
      mFanout = 0;
      mRadio = FALSE;
      mForceTopology = FALSE;
      mWasCommand = FALSE;
      mUart = FALSE;

      mRetryCnt = 0;

	  return call ParentAttr.registerAttr("parent", UINT16, 2);
    }

    //set up data structures as though we're the root of this network
    void setRoot(uint8_t rootId) {
      //mRelOccupiedBits = 1;
      //mRelatives[0] = 0;
      //mRelLevel[rootId][0] = LEVEL_UNKNOWN;
      //mParentIx[rootId] = 0;
    }

    
    /** Given the node id of a routing tree root, determine
	the routing tree id (root parameter of data structures
	to use.
	
	Returns -1 if no more routing trees are available.
    */
    uint8_t getRootId(short rootNode) {
      int i;
      int firstUnknown = -1;

      for (i = 0; i < NUM_ROOTS; i++) {
	if (mRoots[i] != UNKNOWN_ROOT) {
	  if (mRoots[i] == rootNode) {
	    return i;
	  }
	} else if (firstUnknown == -1) {
	    firstUnknown = i;
	}
      }
      if (firstUnknown != -1) {
	mRoots[firstUnknown] = rootNode;
	return firstUnknown;
      }
	
      //HACK -- no more routing trees are available!
      return -1; //something, anyway...
    }

    //check the message to see if it sez we're supposed to be root
    //if so, set up the root and return TRUE, otherwise return FALSE
    bool checkRoot(TOS_MsgPtr msg, uint8_t *rootIdPtr) {
      short root = call QueryProcessor.msgToQueryRoot(msg);
      uint8_t rootId;

      if (root == -1) {
	*rootIdPtr = 0; //default... 
	return FALSE;
      }

      rootId = getRootId(root);
      *rootIdPtr = rootId;
      if (root == TOS_LOCAL_ADDRESS) setRoot(rootId);
      return root == TOS_LOCAL_ADDRESS;
    }
    
     command result_t StdControl.start() {
       return SUCCESS;
     }
     
     command result_t StdControl.stop() {
       return SUCCESS;
     }

    /* Send a 'data' message -- data messages contain information about
   data tuples that should be sent up the routing tree.
   
   REQUIRES:  msg is a message buffer of which the first entry is of
   type DbMsgHdr

   SIGNALS: TINYDB_NETWORK_SUB_MSG_SEND_DONE after message is sent,
   unless an error is returned.

   RETURNS: err_NoError if no error
            err_UnknownError if transmission fails.
*/
     command TinyDBError Network.sendDataMessage(TOS_MsgPtr msg) {
      NetworkMessage *nw = (NetworkMessage *)msg->data;
      bool amRoot;
      uint8_t rootId = 0;

      mMsg = msg;
      mAmId = kDATA_MESSAGE_ID;
      

      amRoot = checkRoot(msg, &rootId);


      //send message bcast, filter at app level

      // amRoot == a base station (connected directly to the pc via the uart)
      if (!mRadio) {

	mRadio = TRUE;
	initHeader(&nw->hdr, amRoot, rootId);
	
	if (amRoot) {
	  mIdx--; //no one else will see this message -- reset the sequence counter
	  if (call SendDataMsg.send(TOS_UART_ADDR, kMSG_LEN, msg) == SUCCESS) {
	    return err_NoError;
	  } else {
	    mRadio = FALSE;
	    return err_MessageSendFailed;
	  }
	} else {
	  mRetryCnt = DATA_RETRIES;
	  if (call SendDataMsg.send(TOS_BCAST_ADDR, kMSG_LEN, msg) == SUCCESS) {
	    return err_NoError;
	  }  else {
	    mIdx--;  //failure -- reuse this index on the next try
	    mRadio = FALSE;
	    return err_MessageSendFailed;