From e8cbbe58ec46a414a5123e745a3faf35e13e2732 Mon Sep 17 00:00:00 2001 From: scipio Date: Thu, 15 Feb 2007 01:27:26 +0000 Subject: [PATCH] MultihopLQI. --- tos/lib/net/lqi/Collection.h | 40 +++ tos/lib/net/lqi/CollectionC.nc | 55 ++++ tos/lib/net/lqi/CollectionSenderC.nc | 22 ++ tos/lib/net/lqi/LQIMultiHopRouter.nc | 98 +++++++ tos/lib/net/lqi/LqiRouteStats.nc | 40 +++ tos/lib/net/lqi/MultiHop.h | 102 ++++++++ tos/lib/net/lqi/MultiHopEngineM.nc | 336 ++++++++++++++++++++++++ tos/lib/net/lqi/MultiHopLQI.nc | 375 +++++++++++++++++++++++++++ tos/lib/net/lqi/RouteControl.nc | 91 +++++++ tos/lib/net/lqi/RouteSelect.nc | 104 ++++++++ 10 files changed, 1263 insertions(+) create mode 100644 tos/lib/net/lqi/Collection.h create mode 100644 tos/lib/net/lqi/CollectionC.nc create mode 100644 tos/lib/net/lqi/CollectionSenderC.nc create mode 100644 tos/lib/net/lqi/LQIMultiHopRouter.nc create mode 100644 tos/lib/net/lqi/LqiRouteStats.nc create mode 100644 tos/lib/net/lqi/MultiHop.h create mode 100644 tos/lib/net/lqi/MultiHopEngineM.nc create mode 100644 tos/lib/net/lqi/MultiHopLQI.nc create mode 100644 tos/lib/net/lqi/RouteControl.nc create mode 100644 tos/lib/net/lqi/RouteSelect.nc diff --git a/tos/lib/net/lqi/Collection.h b/tos/lib/net/lqi/Collection.h new file mode 100644 index 00000000..e20da694 --- /dev/null +++ b/tos/lib/net/lqi/Collection.h @@ -0,0 +1,40 @@ +/* $Id$ */ +/* + * "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 + * @date $Date$ + */ +#ifndef COLLECTION_H +#define COLLECTION_H + +enum { + AM_COLLECTION_DATA = 20, + AM_COLLECTION_CONTROL = 21, + AM_COLLECTION_DEBUG = 22, +}; + +typedef uint8_t collection_id_t; +typedef nx_uint8_t nx_collection_id_t; + +#endif diff --git a/tos/lib/net/lqi/CollectionC.nc b/tos/lib/net/lqi/CollectionC.nc new file mode 100644 index 00000000..554af6ab --- /dev/null +++ b/tos/lib/net/lqi/CollectionC.nc @@ -0,0 +1,55 @@ +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + +/** + * @author Joe Polastre + */ + +#include "MultiHop.h" + +configuration CollectionC { + + provides { + interface StdControl; + interface Receive; + interface Send; + interface Packet; + interface RootControl; + } +} + +implementation { + components LQIMultiHopRouter as Router; + + StdControl = Router; + Receive = Router; + Send = Router; + RootControl = Router; + Packet = Router; +} diff --git a/tos/lib/net/lqi/CollectionSenderC.nc b/tos/lib/net/lqi/CollectionSenderC.nc new file mode 100644 index 00000000..c5ed5901 --- /dev/null +++ b/tos/lib/net/lqi/CollectionSenderC.nc @@ -0,0 +1,22 @@ +/** + * The virtualized collection sender abstraction. + * + * @author Kyle Jamieson + * @author Philip Levis + * @date April 25 2006 + * @see TinyOS Net2-WG + */ + +#include + +generic configuration CollectionSenderC(collection_id_t collectid) { + provides { + interface Send; + interface Packet; + } +} +implementation { + components CollectionC as Router; + Send = Router; + Packet = Router; +} diff --git a/tos/lib/net/lqi/LQIMultiHopRouter.nc b/tos/lib/net/lqi/LQIMultiHopRouter.nc new file mode 100644 index 00000000..c0e8fc02 --- /dev/null +++ b/tos/lib/net/lqi/LQIMultiHopRouter.nc @@ -0,0 +1,98 @@ +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + +/** + * @author Joe Polastre + */ + +#include "MultiHop.h" + +configuration LQIMultiHopRouter { + + provides { + interface StdControl; + interface Receive; + interface Send; + interface RouteControl; + interface LqiRouteStats; + interface Packet; + interface RootControl; + interface CollectionPacket; + } + +} + +implementation { + + components + MultiHopEngineM, + MultiHopLQI, + new AMSenderC(AM_BEACONMSG) as BeaconSender, + new AMReceiverC(AM_BEACONMSG) as BeaconReceiver, + new AMSenderC(AM_DATAMSG) as DataSender, + new AMReceiverC(AM_DATAMSG) as DataReceiver, + new TimerMilliC(), + NoLedsC as LedsC, + RandomC, + ActiveMessageC, + MainC; + + MainC.SoftwareInit -> MultiHopEngineM; + + components CC2420ActiveMessageC as CC2420; + + StdControl = MultiHopLQI.StdControl; + + Receive = MultiHopEngineM; + Send = MultiHopEngineM; + RouteControl = MultiHopEngineM; + LqiRouteStats = MultiHopEngineM; + Packet = MultiHopEngineM; + CollectionPacket = MultiHopEngineM; + RootControl = MultiHopLQI; + + MultiHopEngineM.RouteSelectCntl -> MultiHopLQI.RouteControl; + MultiHopEngineM.RouteSelect -> MultiHopLQI; + MultiHopEngineM.SubSend -> DataSender; + MultiHopEngineM.SubReceive -> DataReceiver; + MultiHopEngineM.Leds -> LedsC; + MultiHopEngineM.AMPacket -> ActiveMessageC; + MultiHopEngineM.SubPacket -> ActiveMessageC; + MultiHopEngineM.PacketAcknowledgements -> ActiveMessageC; + MultiHopEngineM.RootControl -> MultiHopLQI; + + MultiHopLQI.AMSend -> BeaconSender; + MultiHopLQI.Receive -> BeaconReceiver; + MultiHopLQI.Random -> RandomC; + MultiHopLQI.Timer -> TimerMilliC; + MultiHopLQI.LqiRouteStats -> MultiHopEngineM; + MultiHopLQI.CC2420Packet -> CC2420; + MultiHopLQI.AMPacket -> ActiveMessageC; + MultiHopLQI.Packet -> ActiveMessageC; +} diff --git a/tos/lib/net/lqi/LqiRouteStats.nc b/tos/lib/net/lqi/LqiRouteStats.nc new file mode 100644 index 00000000..02cc56a6 --- /dev/null +++ b/tos/lib/net/lqi/LqiRouteStats.nc @@ -0,0 +1,40 @@ +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + + + +/** + * Provides information on how many send failures there have been. + * @author Joe Polastre + */ + + +interface LqiRouteStats { + command uint16_t getSendFailures(); +} diff --git a/tos/lib/net/lqi/MultiHop.h b/tos/lib/net/lqi/MultiHop.h new file mode 100644 index 00000000..1a2750ad --- /dev/null +++ b/tos/lib/net/lqi/MultiHop.h @@ -0,0 +1,102 @@ +// $Id$ + +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + +/* + * + * Authors: Philip Buonadonna, Crossbow, Gilman Tolle + * Date last modified: 2/20/03 + * + */ + +/** + * @author Philip Buonadonna + */ + + +#ifndef _TOS_MULTIHOP_H +#define _TOS_MULTIHOP_H + +#ifndef MHOP_QUEUE_SIZE +#define MHOP_QUEUE_SIZE 2 +#endif + +#ifndef MHOP_HISTORY_SIZE +#define MHOP_HISTORY_SIZE 4 +#endif + +#include "AM.h" +enum { + AM_BEACONMSG = 250, + AM_DATAMSG = 251, + AM_DEBUGPACKET = 3 +}; + +/* Fields of neighbor table */ +typedef struct TOS_MHopNeighbor { + uint16_t addr; // state provided by nbr + uint16_t recv_count; // since last goodness update + uint16_t fail_count; // since last goodness, adjusted by TOs + uint16_t hopcount; + uint8_t goodness; + uint8_t timeouts; // since last recv +} TOS_MHopNeighbor; + +typedef nx_struct lqi_header { + nx_uint16_t originaddr; + nx_int16_t seqno; + nx_int16_t originseqno; + nx_uint16_t hopcount; +} lqi_header_t; + +typedef nx_struct beacon_msg { + nx_uint16_t originaddr; + nx_int16_t seqno; + nx_int16_t originseqno; + nx_uint16_t parent; + nx_uint16_t cost; + nx_uint16_t hopcount; + nx_uint32_t timestamp; +} beacon_msg_t; + +typedef struct DBGEstEntry { + uint16_t id; + uint8_t hopcount; + uint8_t sendEst; +} DBGEstEntry; + +typedef struct DebugPacket { +// uint16_t seqno; + uint16_t estEntries; + DBGEstEntry estList[0]; +} DebugPacket; + +#endif /* _TOS_MULTIHOP_H */ + diff --git a/tos/lib/net/lqi/MultiHopEngineM.nc b/tos/lib/net/lqi/MultiHopEngineM.nc new file mode 100644 index 00000000..220c3a1e --- /dev/null +++ b/tos/lib/net/lqi/MultiHopEngineM.nc @@ -0,0 +1,336 @@ +// $Id$ + +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + +/* + * A simple module that handles multihop packet movement. It accepts + * messages from both applications and the network and does the necessary + * interception and forwarding. + * It interfaces to an algorithmic componenet via RouteSelect. It also acts + * as a front end for RouteControl + */ + + +/* + * Authors: Philip Buonadonna, Alec Woo, Crossbow Inc. + * + */ + +#include "AM.h" +#include "MultiHop.h" + +module MultiHopEngineM { + provides { + interface Init; + interface Receive; + interface Send; + interface Packet; + interface CollectionPacket; + interface RouteControl; + interface LqiRouteStats; + } + uses { + interface Receive as SubReceive; + interface AMSend as SubSend; + interface RouteControl as RouteSelectCntl; + interface RouteSelect; + interface Leds; + interface Packet as SubPacket; + interface AMPacket; + interface RootControl; + interface PacketAcknowledgements; + } +} + +implementation { + + enum { + FWD_QUEUE_SIZE = MHOP_QUEUE_SIZE, // Forwarding Queue + EMPTY = 0xff + }; + + /* Internal storage and scheduling state */ + message_t FwdBuffers[FWD_QUEUE_SIZE]; + message_t *FwdBufList[FWD_QUEUE_SIZE]; + uint8_t FwdBufBusy[FWD_QUEUE_SIZE]; + uint8_t iFwdBufHead, iFwdBufTail; + uint16_t sendFailures = 0; + uint8_t fail_count = 0; + + + + lqi_header_t* getHeader(message_t* msg) { + return (lqi_header_t*) call SubPacket.getPayload(msg, NULL); + } + + /*********************************************************************** + * Initialization + ***********************************************************************/ + + + static void initialize() { + int n; + + for (n=0; n < FWD_QUEUE_SIZE; n++) { + FwdBufList[n] = &FwdBuffers[n]; + FwdBufBusy[n] = 0; + } + + iFwdBufHead = iFwdBufTail = 0; + + sendFailures = 0; + } + + command error_t Init.init() { + initialize(); + return SUCCESS; + } + + + /*********************************************************************** + * Commands and events + ***********************************************************************/ + command error_t Send.send(message_t* pMsg, uint8_t len) { + len += sizeof(lqi_header_t); + if (len > call Packet.maxPayloadLength()) { + return ESIZE; + } + if (call RootControl.isRoot()) { + return FAIL; + } + call RouteSelect.initializeFields(pMsg); + + if (call RouteSelect.selectRoute(pMsg, 0) != SUCCESS) { + return FAIL; + } + call PacketAcknowledgements.requestAck(pMsg); + if (call SubSend.send(call AMPacket.destination(pMsg), pMsg, len) != SUCCESS) { + sendFailures++; + return FAIL; + } + + return SUCCESS; + } + + int8_t get_buff(){ + uint8_t n; + for (n=0; n < FWD_QUEUE_SIZE; n++) { + uint8_t done = 0; + atomic{ + if(FwdBufBusy[n] == 0){ + FwdBufBusy[n] = 1; + done = 1; + } + } + if(done == 1) return n; + + } + return -1; + } + + int8_t is_ours(message_t* ptr){ + uint8_t n; + for (n=0; n < FWD_QUEUE_SIZE; n++) { + if(FwdBufList[n] == ptr){ + return n; + } + } + return -1; + } + + static message_t* mForward(message_t* msg) { + message_t* newMsg = msg; + int8_t buf = get_buff(); + + if (call RootControl.isRoot()) { + return signal Receive.receive(msg, call Packet.getPayload(msg, NULL), call Packet.payloadLength(msg)); + } + + if (buf == -1) { + dbg("LQI", "Dropped packet due to no space in queue.\n"); + return msg; + } + + if ((call RouteSelect.selectRoute(msg, 0)) != SUCCESS) { + FwdBufBusy[(uint8_t)buf] = 0; + return msg; + } + + // Failures at the send level do not cause the seq. number space to be + // rolled back properly. This is somewhat broken. + call PacketAcknowledgements.requestAck(msg); + if (call SubSend.send(call AMPacket.destination(msg), + msg, + call SubPacket.payloadLength(msg) == SUCCESS)) { + newMsg = FwdBufList[(uint8_t)buf]; + FwdBufList[(uint8_t)buf] = msg; + } + else{ + FwdBufBusy[(uint8_t)buf] = 0; + sendFailures++; + } + return newMsg; + } + + event message_t* SubReceive.receive(message_t* msg, void* payload, uint8_t len) { + return mForward(msg); + } + + + event void SubSend.sendDone(message_t* msg, error_t success) { + int8_t buf; + if (!call PacketAcknowledgements.wasAcked(msg) && + call AMPacket.destination(msg) != TOS_BCAST_ADDR && + fail_count < 5){ + call RouteSelect.selectRoute(msg, 1); + if (call SubSend.send(call AMPacket.destination(msg), + msg, + call SubPacket.payloadLength(msg)) == SUCCESS) { + fail_count ++; + } else { + sendFailures++; + } + } + + fail_count = 0; + + buf = is_ours(msg); + + if (buf != -1) { // Msg was from forwarding queue + FwdBufBusy[(uint8_t)buf] = 0; + } else { + signal Send.sendDone(msg, success); + } + } + + + command uint16_t RouteControl.getParent() { + return call RouteSelectCntl.getParent(); + } + + command uint8_t RouteControl.getQuality() { + return call RouteSelectCntl.getQuality(); + } + + command uint8_t RouteControl.getDepth() { + return call RouteSelectCntl.getDepth(); + } + + command uint8_t RouteControl.getOccupancy() { + uint16_t uiOutstanding = (uint16_t)iFwdBufTail - (uint16_t)iFwdBufHead; + uiOutstanding %= FWD_QUEUE_SIZE; + return (uint8_t)uiOutstanding; + } + + + command error_t RouteControl.setUpdateInterval(uint16_t Interval) { + return call RouteSelectCntl.setUpdateInterval(Interval); + } + + command error_t RouteControl.manualUpdate() { + return call RouteSelectCntl.manualUpdate(); + } + + command uint16_t LqiRouteStats.getSendFailures() { + return sendFailures; + } + + command void Packet.clear(message_t* msg) { + + } + + command void* Send.getPayload(message_t* m) { + return call Packet.getPayload(m, NULL); + } + + command uint8_t Send.maxPayloadLength() { + return call Packet.maxPayloadLength(); + } + + command error_t Send.cancel(message_t* m) { + return FAIL; + } + + command void* Receive.getPayload(message_t* m, uint8_t* len) { + return call Packet.getPayload(m, len); + } + + command uint8_t Receive.payloadLength(message_t* m) { + return call Packet.payloadLength(m); + } + + command uint8_t Packet.payloadLength(message_t* msg) { + return call SubPacket.payloadLength(msg) - sizeof(lqi_header_t); + } + command void Packet.setPayloadLength(message_t* msg, uint8_t len) { + call SubPacket.setPayloadLength(msg, len + sizeof(lqi_header_t)); + } + command uint8_t Packet.maxPayloadLength() { + return (call SubPacket.maxPayloadLength() - sizeof(lqi_header_t)); + } + command void* Packet.getPayload(message_t* msg, uint8_t* len) { + void* rval = call SubPacket.getPayload(msg, len); + *len -= sizeof(lqi_header_t); + rval += sizeof(lqi_header_t); + return rval; + } + + command am_addr_t CollectionPacket.getOrigin(message_t* msg) { + lqi_header_t* hdr = getHeader(msg); + return hdr->originaddr; + } + + command void CollectionPacket.setOrigin(message_t* msg, am_addr_t addr) { + lqi_header_t* hdr = getHeader(msg); + hdr->originaddr = addr; + } + + command collection_id_t CollectionPacket.getType(message_t* msg) { + return 0; + } + + command void CollectionPacket.setType(message_t* msg, collection_id_t id) {} + + command uint8_t CollectionPacket.getSequenceNumber(message_t* msg) { + lqi_header_t* hdr = getHeader(msg); + return hdr->originseqno; + } + + command void CollectionPacket.setSequenceNumber(message_t* msg, uint8_t seqno) { + lqi_header_t* hdr = getHeader(msg); + hdr->originseqno = seqno; + } + + default event void Send.sendDone(message_t* pMsg, error_t success) {} + + + +} + diff --git a/tos/lib/net/lqi/MultiHopLQI.nc b/tos/lib/net/lqi/MultiHopLQI.nc new file mode 100644 index 00000000..9259b3e4 --- /dev/null +++ b/tos/lib/net/lqi/MultiHopLQI.nc @@ -0,0 +1,375 @@ +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + + + +/* + * Authors: Gilman Tolle + */ + + +#include "MultiHop.h" + +module MultiHopLQI { + + provides { + interface Init; + interface StdControl; + interface RouteSelect; + interface RouteControl; + interface RootControl; + } + + uses { + interface Timer; + interface AMSend; + interface Receive; + interface Random; + interface Packet; + interface AMPacket; + interface LqiRouteStats; + interface CC2420Packet; + } +} + +implementation { + + enum { + BASE_STATION_ADDRESS = 0, + BEACON_PERIOD = 32, + BEACON_TIMEOUT = 8, + }; + + enum { + ROUTE_INVALID = 0xff + }; + + bool isRoot = FALSE; + + message_t msgBuf; + bool msgBufBusy; + + uint16_t gbCurrentParent; + uint16_t gbCurrentParentCost; + uint16_t gbCurrentLinkEst; + uint8_t gbCurrentHopCount; + uint16_t gbCurrentCost; + + uint8_t gLastHeard; + + int16_t gCurrentSeqNo; + + uint16_t gUpdateInterval; + + uint8_t gRecentIndex; + uint16_t gRecentPacketSender[MHOP_HISTORY_SIZE]; + int16_t gRecentPacketSeqNo[MHOP_HISTORY_SIZE]; + + uint8_t gRecentOriginIndex; + uint16_t gRecentOriginPacketSender[MHOP_HISTORY_SIZE]; + int16_t gRecentOriginPacketSeqNo[MHOP_HISTORY_SIZE]; + + uint16_t adjustLQI(uint8_t val) { + uint16_t result = (80 - (val - 50)); + result = (((result * result) >> 3) * result) >> 3; + return result; + } + + lqi_header_t* getHeader(message_t* msg) { + return (lqi_header_t*)call Packet.getPayload(msg, NULL); + } + beacon_msg_t* getBeacon(message_t* msg) { + return (beacon_msg_t*)call Packet.getPayload(msg, NULL); + } + + task void SendRouteTask() { + beacon_msg_t* bMsg = getBeacon(&msgBuf); + uint8_t length = sizeof(beacon_msg_t); + + dbg("LQI","MultiHopRSSI Sending route update msg.\n"); + + if (gbCurrentParent != TOS_BCAST_ADDR) { + dbg("LQO","MultiHopRSSI: Parent = %d\n", gbCurrentParent); + } + + if (msgBufBusy) { + post SendRouteTask(); + return; + } + + dbg("LQI","MultiHopRSSI: Current cost: %d.\n", + gbCurrentParentCost + gbCurrentLinkEst); + + if (isRoot) { + bMsg->parent = TOS_NODE_ID; + bMsg->cost = 0; + bMsg->originaddr = TOS_NODE_ID; + bMsg->hopcount = 0; + bMsg->originseqno = gCurrentSeqNo; + bMsg->seqno = gCurrentSeqNo++; + } + else { + bMsg->parent = gbCurrentParent; + bMsg->cost = gbCurrentParentCost + gbCurrentLinkEst; + bMsg->originaddr = TOS_NODE_ID; + bMsg->hopcount = gbCurrentHopCount; + bMsg->originseqno = gCurrentSeqNo; + bMsg->seqno = gCurrentSeqNo++; + } + + if (call AMSend.send(TOS_BCAST_ADDR, &msgBuf, length) == SUCCESS) { + msgBufBusy = TRUE; + } + } + + task void TimerTask() { + uint8_t val; + val = ++gLastHeard; + if (!isRoot && (val > BEACON_TIMEOUT)) { + gbCurrentParent = TOS_BCAST_ADDR; + gbCurrentParentCost = 0x7fff; + gbCurrentLinkEst = 0x7fff; + gbCurrentHopCount = ROUTE_INVALID; + gbCurrentCost = 0xfffe; + } + post SendRouteTask(); + } + + command error_t Init.init() { + int n; + + gRecentIndex = 0; + for (n = 0; n < MHOP_HISTORY_SIZE; n++) { + gRecentPacketSender[n] = TOS_BCAST_ADDR; + gRecentPacketSeqNo[n] = 0; + } + + gRecentOriginIndex = 0; + for (n = 0; n < MHOP_HISTORY_SIZE; n++) { + gRecentOriginPacketSender[n] = TOS_BCAST_ADDR; + gRecentOriginPacketSeqNo[n] = 0; + } + + gbCurrentParent = TOS_BCAST_ADDR; + gbCurrentParentCost = 0x7fff; + gbCurrentLinkEst = 0x7fff; + gbCurrentHopCount = ROUTE_INVALID; + gbCurrentCost = 0xfffe; + + gCurrentSeqNo = 0; + gUpdateInterval = BEACON_PERIOD; + msgBufBusy = FALSE; + + return SUCCESS; + } + + command error_t RootControl.setRoot() { + isRoot = TRUE; + return SUCCESS; + } + + command error_t RootControl.unsetRoot() { + isRoot = FALSE; + return SUCCESS; + } + + command bool RootControl.isRoot() { + return isRoot; + } + + command error_t StdControl.start() { + gLastHeard = 0; + call Timer.startOneShot(call Random.rand32() % (1024 * gUpdateInterval)); + return SUCCESS; + } + + command error_t StdControl.stop() { + call Timer.stop(); + return SUCCESS; + } + + command bool RouteSelect.isActive() { + return TRUE; + } + + command error_t RouteSelect.selectRoute(message_t* msg, uint8_t resend) { + int i; + lqi_header_t* hdr = getHeader(msg); + if (isRoot) { + return FAIL; + } + + if (hdr->originaddr != TOS_NODE_ID && resend == 0) { + // supress duplicate packets + for (i = 0; i < MHOP_HISTORY_SIZE; i++) { + if ((gRecentPacketSender[i] == call AMPacket.source(msg)) && + (gRecentPacketSeqNo[i] == hdr->seqno)) { + return FAIL; + } + } + + gRecentPacketSender[gRecentIndex] = call AMPacket.source(msg); + gRecentPacketSeqNo[gRecentIndex] = hdr->seqno; + gRecentIndex = (gRecentIndex + 1) % MHOP_HISTORY_SIZE; + + // supress multihop cycles and try to break out of it + for (i = 0; i < MHOP_HISTORY_SIZE; i++) { + if ((gRecentOriginPacketSender[i] == hdr->originaddr) && + (gRecentOriginPacketSeqNo[i] == hdr->originseqno)) { + gbCurrentParentCost = 0x7fff; + gbCurrentLinkEst = 0x7fff; + gbCurrentParent = TOS_BCAST_ADDR; + gbCurrentHopCount = ROUTE_INVALID; + return FAIL; + } + } + gRecentOriginPacketSender[gRecentOriginIndex] = hdr->originaddr; + gRecentOriginPacketSeqNo[gRecentOriginIndex] = hdr->originseqno; + gRecentOriginIndex = (gRecentOriginIndex + 1) % MHOP_HISTORY_SIZE; + } + + if (resend == 0) { + hdr->seqno = gCurrentSeqNo++; + } + + call AMPacket.setDestination(msg, gbCurrentParent); + + return SUCCESS; + } + + command error_t RouteSelect.initializeFields(message_t* msg) { + lqi_header_t* header = (lqi_header_t*)call Packet.getPayload(msg, NULL); + + header->originaddr = TOS_NODE_ID; + header->originseqno = gCurrentSeqNo; + + if (isRoot) { + header->hopcount = 0; + } + else { + header->hopcount = gbCurrentHopCount; + } + + return SUCCESS; + } + + command uint8_t* RouteSelect.getBuffer(message_t* Msg, uint16_t* Len) { + + } + + + command uint16_t RouteControl.getParent() { + return gbCurrentParent; + } + + command uint8_t RouteControl.getQuality() { + return gbCurrentLinkEst; + } + + command uint8_t RouteControl.getDepth() { + return gbCurrentHopCount; + } + + command uint8_t RouteControl.getOccupancy() { + return 0; + } + + command error_t RouteControl.setUpdateInterval(uint16_t Interval) { + + gUpdateInterval = Interval; + return SUCCESS; + } + + command error_t RouteControl.manualUpdate() { + post SendRouteTask(); + return SUCCESS; + } + + + event void Timer.fired() { + post TimerTask(); + call Timer.startOneShot(1024 * gUpdateInterval + 1); + } + + event message_t* Receive.receive(message_t* msg, void* payload, uint8_t len) { + if (isRoot) { + return msg; + } + else { + beacon_msg_t* bMsg = (beacon_msg_t*)payload; + am_addr_t source = call AMPacket.source(msg); + uint8_t lqi = call CC2420Packet.getLqi(msg); + + if (source == gbCurrentParent) { + // try to prevent cycles + if (bMsg->parent != TOS_NODE_ID) { + gLastHeard = 0; + gbCurrentParentCost = bMsg->cost; + gbCurrentLinkEst = adjustLQI(lqi); + gbCurrentHopCount = bMsg->hopcount + 1; + } + else { + gLastHeard = 0; + gbCurrentParentCost = 0x7fff; + gbCurrentLinkEst = 0x7fff; + gbCurrentParent = TOS_BCAST_ADDR; + gbCurrentHopCount = ROUTE_INVALID; + } + + } else { + + /* if the message is not from my parent, + compare the message's cost + link estimate to my current cost, + switch if necessary */ + + // make sure you don't pick a parent that creates a cycle + if (((uint32_t) bMsg->cost + (uint32_t) adjustLQI(lqi) + < + ((uint32_t) gbCurrentParentCost + (uint32_t) gbCurrentLinkEst) - + (((uint32_t) gbCurrentParentCost + (uint32_t) gbCurrentLinkEst) >> 2) + ) && + (bMsg->parent != TOS_NODE_ID)) { + gLastHeard = 0; + gbCurrentParent = call AMPacket.source(msg); + gbCurrentParentCost = bMsg->cost; + gbCurrentLinkEst = adjustLQI(lqi); + gbCurrentHopCount = bMsg->hopcount + 1; + } + } + } + + return msg; + } + + event void AMSend.sendDone(message_t* msg, error_t success) { + msgBufBusy = FALSE; + } + +} + diff --git a/tos/lib/net/lqi/RouteControl.nc b/tos/lib/net/lqi/RouteControl.nc new file mode 100644 index 00000000..fecba989 --- /dev/null +++ b/tos/lib/net/lqi/RouteControl.nc @@ -0,0 +1,91 @@ +// $Id$ + +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ + +/* + * Authors: Phil Buonadonna + * Rev: $Id$ + */ + +/** + * Control/Monitor interface to a routing component + * @author Phil Buonadonna + */ + +interface RouteControl { + + /** + * Get this node's present parent address. + * + * @return The address of the parent + */ + command uint16_t getParent(); + + /** + * Get this node's depth in the network + * + * @return The network depth. + */ + command uint8_t getDepth(); + + + /** + * Return length of the routing forwarding queue + * + * @return The number of outstanding entries in the queue. + */ + command uint8_t getOccupancy(); + + /** + * Get a measure of goodness for the current parent + * + * @return A value between 0-256 where 256 represent the best + * goodness + */ + command uint8_t getQuality(); + + /** + * Set the routing componenets internal update interval. + * + * @param The duration, in seconds, of successive routing + * updates. + * + * @return SUCCESS if the operation succeeded. + */ + command error_t setUpdateInterval(uint16_t Interval); + + /** + * Queue a manual update of the routing state. This may or may + * not include the transmission of a message. + * + * @return SUCCESS if a route update was queued. + */ + command error_t manualUpdate(); +} diff --git a/tos/lib/net/lqi/RouteSelect.nc b/tos/lib/net/lqi/RouteSelect.nc new file mode 100644 index 00000000..ab63783a --- /dev/null +++ b/tos/lib/net/lqi/RouteSelect.nc @@ -0,0 +1,104 @@ +// $Id$ + +/* tab:4 + * "Copyright (c) 2000-2003 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." + * + * Copyright (c) 2002-2003 Intel Corporation + * All rights reserved. + * + * This file is distributed under the terms in the attached INTEL-LICENSE + * file. If you do not find these files, copies can be found by writing to + * Intel Research Berkeley, 2150 Shattuck Avenue, Suite 1300, Berkeley, CA, + * 94704. Attention: Intel License Inquiry. + */ +/* + * Authors: Philip Levis + * Date last modified: 8/12/02 + * + * The RouteSelect interface is part of the TinyOS ad-hoc routing + * system architecture. The component that keeps track of routing + * information and makes route selection decisions provides this + * interface. When a Send component wants to send a packet, it passes + * it to RouteSelect for its routing information to be filled in. This + * way, the Send component is entirely unaware of the routing + * header/footer structure. + */ + +/** + * Interface to a route selection component in the TinyOS ad-hoc + * system architecture. + * @author Philip Levis + */ + +#include "AM.h" + +interface RouteSelect { + + /** + * Whether there is currently a valid route. + * + * @return Whether there is a valid route. + */ + command bool isActive(); + + /** + * Select a route and fill in all of the necessary routing + * information to a packet. + * + * @param msg Message to select route for and fill in routing information. + * + * @return Whether a route was selected succesfully. On FAIL the + * packet should not be sent. + * + */ + + command error_t selectRoute(message_t* msg, uint8_t resend); + + + /** + * Given a TOS_MstPtr, initialize its routing fields to a known + * state, specifying that the message is originating from this node. + * This known state can then be used by selectRoute() to fill in + * the necessary data. + * + * @param msg Message to select route for and fill in init data. + * + * @return Should always return SUCCESS. + * + */ + + command error_t initializeFields(message_t* msg); + + + /** + * Given a TinyOS message buffer, provide a pointer to the data + * buffer within it that an application can use as well as its + * length. Unlike the getBuffer of the Send interface, this can + * be called freely and does not modify the buffer. + * + * @param msg The message to get the data region of. + * + * @param length Pointer to a field to store the length of the data region. + * + * @return A pointer to the data region. + */ + + command uint8_t* getBuffer(message_t* msg, uint16_t* len); +} -- 2.39.2