RHMesh.h

00001 // RHMesh.h
00002 //
00003 // Author: Mike McCauley (mikem@airspayce.com)
00004 // Copyright (C) 2011 Mike McCauley
00005 // $Id: RHMesh.h,v 1.15 2015/08/13 02:45:47 mikem Exp $
00006 
00007 #ifndef RHMesh_h
00008 #define RHMesh_h
00009 
00010 #include <RHRouter.h>
00011 
00012 // Types of RHMesh message, used to set msgType in the RHMeshHeader
00013 #define RH_MESH_MESSAGE_TYPE_APPLICATION                    0
00014 #define RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST        1
00015 #define RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_RESPONSE       2
00016 #define RH_MESH_MESSAGE_TYPE_ROUTE_FAILURE                  3
00017 
00018 // Timeout for address resolution in milliecs
00019 #define RH_MESH_ARP_TIMEOUT 4000
00020 
00021 /////////////////////////////////////////////////////////////////////
00022 /// \class RHMesh RHMesh.h <RHMesh.h>
00023 /// \brief RHRouter subclass for sending addressed, optionally acknowledged datagrams
00024 /// multi-hop routed across a network, with automatic route discovery
00025 ///
00026 /// Manager class that extends RHRouter to add automatic route discovery within a mesh of adjacent nodes, 
00027 /// and route signalling.
00028 ///
00029 /// Unlike RHRouter, RHMesh can be used in networks where the network topology is fluid, or unknown, 
00030 /// or if nodes can mode around or go in or out of service. When a node wants to send a 
00031 /// message to another node, it will automatically discover a route to the destination node and use it. 
00032 /// If the route becomes unavailable, a new route will be discovered.
00033 ///
00034 /// \par Route Discovery
00035 ///
00036 /// When a RHMesh mesh node is initialised, it doe not know any routes to any other nodes 
00037 /// (see RHRouter for details on route and the routing table).
00038 /// When you attempt to send a message with sendtoWait, will first check to see if there is a route to the 
00039 /// destinastion node in the routing tabl;e. If not, it wil initialite 'Route Discovery'.
00040 /// When a node needs to discover a route to another node, it broadcasts MeshRouteDiscoveryMessage 
00041 /// with a message type of RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST. 
00042 /// Any node that receives such a request checks to see if it is a request for a route to itself
00043 /// (in which case it makes a unicast reply to the originating node with a 
00044 /// MeshRouteDiscoveryMessage 
00045 /// with a message type of RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_RESPONSE) 
00046 /// otherwise it rebroadcasts the request, after adding itself to the list of nodes visited so 
00047 /// far by the request.
00048 ///
00049 /// If a node receives a RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST that already has itself 
00050 /// listed in the visited nodes, it knows it has already seen and rebroadcast this request, 
00051 /// and threfore ignores it. This prevents broadcast storms.
00052 /// When a node receives a RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST it can use the list of 
00053 /// nodes aready visited to deduce routes back towards the originating (requesting node). 
00054 /// This also means that when the destination node of the request is reached, it (and all 
00055 /// the previous nodes the request visited) will have a route back to the originating node. 
00056 /// This means the unicast RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_RESPONSE 
00057 /// reply will be routed successfully back to the original route requester.
00058 ///
00059 /// The RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_RESPONSE sent back by the destination node contains 
00060 /// the full list of nodes that were visited on the way to the destination.
00061 /// Therefore, intermediate nodes that route the reply back towards the originating node can use the 
00062 /// node list in the reply to deduce routes to all the nodes between it and the destination node.
00063 ///
00064 /// Therefore, RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST and 
00065 /// RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_RESPONSE together ensure the original requester and all 
00066 /// the intermediate nodes know how to route to the source and destination nodes and every node along the path.
00067 ///
00068 /// Note that there is a race condition here that can effect routing on multipath routes. For example, 
00069 /// if the route to the destination can traverse several paths, last reply from the destination 
00070 /// will be the one used.
00071 ///
00072 /// \par Route Failure
00073 ///
00074 /// RHRouter (and therefore RHMesh) use reliable hop-to-hop delivery of messages using 
00075 /// hop-to-hop acknowledgements, but not end-to-end acknowledgements. When sendtoWait() returns, 
00076 /// you know that the message has been delivered to the next hop, but not if it is (or even if it can be) 
00077 /// delivered to the destination node. If during the course of hop-to-hop routing of a message, 
00078 /// one of the intermediate RHMesh nodes finds it cannot deliver to the next hop 
00079 /// (say due to a lost route or no acknwledgement from the next hop), it replies to the 
00080 /// originator with a unicast MeshRouteFailureMessage RH_MESH_MESSAGE_TYPE_ROUTE_FAILURE message. 
00081 /// Intermediate nodes (on the way beack to the originator)
00082 /// and the originating node use this message to delete the route to the destination 
00083 /// node of the original message. This means that if a route to a destination becomes unusable 
00084 /// (either because an intermediate node is off the air, or has moved out of range) a new route 
00085 /// will be established the next time a message is to be sent.
00086 ///
00087 /// \par Message Format
00088 ///
00089 /// RHMesh uses a number of message formats layered on top of RHRouter:
00090 /// - MeshApplicationMessage (message type RH_MESH_MESSAGE_TYPE_APPLICATION). 
00091 ///   Carries an application layer message for the caller of RHMesh
00092 /// - MeshRouteDiscoveryMessage (message types RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST 
00093 ///   and RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_RESPONSE). Carries Route Discovery messages 
00094 ///   (broadcast) and replies (unicast).
00095 /// - MeshRouteFailureMessage (message type RH_MESH_MESSAGE_TYPE_ROUTE_FAILURE) Informs nodes of 
00096 ///   route failures.
00097 ///
00098 /// Part of the Arduino RH library for operating with HopeRF RH compatible transceivers 
00099 /// (see http://www.hoperf.com)
00100 ///
00101 /// \par Memory
00102 ///
00103 /// RHMesh programs require significant amount of SRAM, often approaching 2kbytes, 
00104 /// which is beyond or at the limits of some Arduinos and other processors. Programs 
00105 /// with additional software besides basic RHMesh programs may well require even more. If you have insufficient
00106 /// SRAM for your program, it may result in failure to run, or wierd crashes and other hard to trace behaviour.
00107 /// In this event you should consider a processor with more SRAM, such as the MotienoMEGA with 16k
00108 /// (https://lowpowerlab.com/shop/moteinomega) or others.
00109 ///
00110 /// \par Performance
00111 /// This class (in the interests of simple implemtenation and low memory use) does not have
00112 /// message queueing. This means that only one message at a time can be handled. Message transmission 
00113 /// failures can have a severe impact on network performance.
00114 /// If you need high performance mesh networking under all conditions consider XBee or similar.
00115 class RHMesh : public RHRouter
00116 {
00117 public:
00118 
00119     /// The maximum length permitted for the application payload data in a RHMesh message
00120     #define RH_MESH_MAX_MESSAGE_LEN (RH_ROUTER_MAX_MESSAGE_LEN - sizeof(RHMesh::MeshMessageHeader))
00121 
00122     /// Structure of the basic RHMesh header.
00123     typedef struct
00124     {
00125     uint8_t             msgType;  ///< Type of RHMesh message, one of RH_MESH_MESSAGE_TYPE_*
00126     } MeshMessageHeader;
00127 
00128     /// Signals an application layer message for the caller of RHMesh
00129     typedef struct
00130     {
00131     MeshMessageHeader   header; ///< msgType = RH_MESH_MESSAGE_TYPE_APPLICATION 
00132     uint8_t             data[RH_MESH_MAX_MESSAGE_LEN]; ///< Application layer payload data
00133     } MeshApplicationMessage;
00134 
00135     /// Signals a route discovery request or reply (At present only supports physical dest addresses of length 1 octet)
00136     typedef struct
00137     {
00138     MeshMessageHeader   header;  ///< msgType = RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_*
00139     uint8_t             destlen; ///< Reserved. Must be 1.g
00140     uint8_t             dest;    ///< The address of the destination node whose route is being sought
00141     uint8_t             route[RH_MESH_MAX_MESSAGE_LEN - 1]; ///< List of node addresses visited so far. Length is implcit
00142     } MeshRouteDiscoveryMessage;
00143 
00144     /// Signals a route failure
00145     typedef struct
00146     {
00147     MeshMessageHeader   header; ///< msgType = RH_MESH_MESSAGE_TYPE_ROUTE_FAILURE
00148     uint8_t             dest; ///< The address of the destination towards which the route failed
00149     } MeshRouteFailureMessage;
00150 
00151     /// Constructor. 
00152     /// \param[in] driver The RadioHead driver to use to transport messages.
00153     /// \param[in] thisAddress The address to assign to this node. Defaults to 0
00154     RHMesh(RHGenericDriver& driver, uint8_t thisAddress = 0);
00155 
00156     /// Sends a message to the destination node. Initialises the RHRouter message header 
00157     /// (the SOURCE address is set to the address of this node, HOPS to 0) and calls 
00158     /// route() which looks up in the routing table the next hop to deliver to.
00159     /// If no route is known, initiates route discovery and waits for a reply.
00160     /// Then sends the message to the next hop
00161     /// Then waits for an acknowledgement from the next hop 
00162     /// (but not from the destination node (if that is different).
00163     /// \param [in] buf The application message data
00164     /// \param [in] len Number of octets in the application message data. 0 is permitted
00165     /// \param [in] dest The destination node address. If the address is RH_BROADCAST_ADDRESS (255)
00166     /// the message will be broadcast to all the nearby nodes, but not routed or relayed.
00167     /// \param [in] flags Optional flags for use by subclasses or application layer, 
00168     ///             delivered end-to-end to the dest address. The receiver can recover the flags with recvFromAck().
00169     /// \return The result code:
00170     ///         - RH_ROUTER_ERROR_NONE Message was routed and delivered to the next hop 
00171     ///           (not necessarily to the final dest address)
00172     ///         - RH_ROUTER_ERROR_NO_ROUTE There was no route for dest in the local routing table
00173     ///         - RH_ROUTER_ERROR_UNABLE_TO_DELIVER Not able to deliver to the next hop 
00174     ///           (usually because it dod not acknowledge due to being off the air or out of range
00175     uint8_t sendtoWait(uint8_t* buf, uint8_t len, uint8_t dest, uint8_t flags = 0);
00176 
00177     /// Starts the receiver if it is not running already, processes and possibly routes any received messages
00178     /// addressed to other nodes
00179     /// and delivers any messages addressed to this node.
00180     /// If there is a valid application layer message available for this node (or RH_BROADCAST_ADDRESS), 
00181     /// send an acknowledgement to the last hop
00182     /// address (blocking until this is complete), then copy the application message payload data
00183     /// to buf and return true
00184     /// else return false. 
00185     /// If a message is copied, *len is set to the length..
00186     /// If from is not NULL, the originator SOURCE address is placed in *source.
00187     /// If to is not NULL, the DEST address is placed in *dest. This might be this nodes address or 
00188     /// RH_BROADCAST_ADDRESS. 
00189     /// This is the preferred function for getting messages addressed to this node.
00190     /// If the message is not a broadcast, acknowledge to the sender before returning.
00191     /// \param[in] buf Location to copy the received message
00192     /// \param[in,out] len Available space in buf. Set to the actual number of octets copied.
00193     /// \param[in] source If present and not NULL, the referenced uint8_t will be set to the SOURCE address
00194     /// \param[in] dest If present and not NULL, the referenced uint8_t will be set to the DEST address
00195     /// \param[in] id If present and not NULL, the referenced uint8_t will be set to the ID
00196     /// \param[in] flags If present and not NULL, the referenced uint8_t will be set to the FLAGS
00197     /// (not just those addressed to this node).
00198     /// \return true if a valid message was received for this node and copied to buf
00199     bool recvfromAck(uint8_t* buf, uint8_t* len, uint8_t* source = NULL, uint8_t* dest = NULL, uint8_t* id = NULL, uint8_t* flags = NULL);
00200 
00201     /// Starts the receiver if it is not running already.
00202     /// Similar to recvfromAck(), this will block until either a valid application layer 
00203     /// message available for this node
00204     /// or the timeout expires. 
00205     /// \param[in] buf Location to copy the received message
00206     /// \param[in,out] len Available space in buf. Set to the actual number of octets copied.
00207     /// \param[in] timeout Maximum time to wait in milliseconds
00208     /// \param[in] source If present and not NULL, the referenced uint8_t will be set to the SOURCE address
00209     /// \param[in] dest If present and not NULL, the referenced uint8_t will be set to the DEST address
00210     /// \param[in] id If present and not NULL, the referenced uint8_t will be set to the ID
00211     /// \param[in] flags If present and not NULL, the referenced uint8_t will be set to the FLAGS
00212     /// (not just those addressed to this node).
00213     /// \return true if a valid message was copied to buf
00214     bool recvfromAckTimeout(uint8_t* buf, uint8_t* len,  uint16_t timeout, uint8_t* source = NULL, uint8_t* dest = NULL, uint8_t* id = NULL, uint8_t* flags = NULL);
00215 
00216 protected:
00217 
00218     /// Internal function that inspects messages being received and adjusts the routing table if necessary.
00219     /// Called by recvfromAck() immediately after it gets the message from RHReliableDatagram
00220     /// \param [in] message Pointer to the RHRouter message that was received.
00221     /// \param [in] messageLen Length of message in octets
00222     virtual void peekAtMessage(RoutedMessage* message, uint8_t messageLen);
00223 
00224     /// Internal function that inspects messages being received and adjusts the routing table if necessary.
00225     /// This is virtual, which lets subclasses override or intercept the route() function.
00226     /// Called by sendtoWait after the message header has been filled in.
00227     /// \param [in] message Pointer to the RHRouter message to be sent.
00228     /// \param [in] messageLen Length of message in octets
00229     virtual uint8_t route(RoutedMessage* message, uint8_t messageLen);
00230 
00231     /// Try to resolve a route for the given address. Blocks while discovering the route
00232     /// which may take up to 4000 msec.
00233     /// Virtual so subclasses can override.
00234     /// \param [in] address The physical address to resolve
00235     /// \return true if the address was resolved and added to the local routing table
00236     virtual bool doArp(uint8_t address);
00237 
00238     /// Tests if the given address of length addresslen is indentical to the
00239     /// physical address of this node.
00240     /// RHMesh always implements physical addresses as the 1 octet address of the node
00241     /// given by _thisAddress
00242     /// Called by recvfromAck() to test whether a RH_MESH_MESSAGE_TYPE_ROUTE_DISCOVERY_REQUEST
00243     /// is for this node.
00244     /// Subclasses may want to override to implement more complicated or longer physical addresses
00245     /// \param [in] address Address of the pyysical addres being tested
00246     /// \param [in] addresslen Lengthof the address in bytes
00247     /// \return true if the physical address of this node is identical to address
00248     virtual bool isPhysicalAddress(uint8_t* address, uint8_t addresslen);
00249 
00250 private:
00251     /// Temporary message buffer
00252     static uint8_t _tmpMessage[RH_ROUTER_MAX_MESSAGE_LEN];
00253 
00254 };
00255 
00256 /// @example rf22_mesh_client.pde
00257 /// @example rf22_mesh_server1.pde
00258 /// @example rf22_mesh_server2.pde
00259 /// @example rf22_mesh_server3.pde
00260 
00261 #endif
00262