GPSNet.h

// GPSNet.h
// Author: Mike McCauley
// Copyright (C) 2013 Mike McCauley
// $Id: GPSNet.h,v 1.1 2013/02/20 06:43:38 mikem Exp mikem $

///  \mainpage GPSNet library for Arduino 
///
/// This is the Arduino GPSNet library.
/// GPSNet is an Arduino library and example sketch that provides a radio broadcast mesh
/// network among a number of GPS+RFM22 radio equipped nodes, such that all nodes in the
/// network know the GPS position of all other nodes.
/// 
/// This is intended to help organisations that need visibility of the location of
/// a number of independent mobile units (people, vehicles etc), such as might be
/// used by emergency services, cooperating fishing vessels etc.
/// 
/// The provided sample sketch works with any serial GPS receiver and RF22 data
/// radio transceivers on the 433MHz ISR band.
///
/// The version of the package that this documentation refers to can be downloaded 
/// from http://www.airspayce.com/mikem/arduino/GPSNet/GPSNet-1.6.zip
/// You can find the latest version at http://www.airspayce.com/mikem/arduino/GPSNet
///
/// \par Operation
/// 
/// GPSnet forms a loosly connected radio mesh network based on broadcast data
/// messages. The main principles of operation are:
/// 
/// - Every node has a GPS receiver and radio transceiver.
/// - Every node has a unique NodeID string (stored in EEPROM).
/// - Periodically every node broadcasts a message with its 
///   NodeID, and GPS position and timestamp.
/// - Every node listens for broadcasts from other nodes, and keeps in memory 
///   the most recent data from each node.
/// - Every node periodically rebroadcasts the position of nodes it knows
///   about, with the preference given to data that changed most recently
///   (either from its own GPS or updates heard from other nodes).
/// 
/// Additionally:
/// - Each node throttles its message boadcast rate depending on how many other
///   nodes are within range.
/// - Different sets of nodes can operate independent of each other on different
///   radio channels.
/// - Each node can be connected to an external device responsible for displaying
///   the relative location of all known nodes, or transmitting them by some other
///   technology to a central location
/// 
/// This means that every node will eventually receive the position of all the
/// other nodes it can hear (either directly or indirectly). The latest position
/// of each node will propagate through the entire connected network (irrespective
/// of the network topology), giving the most widespread possible knowledge of the
/// entire fleet to every node, along with the age of the data.
/// 
/// Every node can be a source of information about the entire fleet to a locally 
/// connected PC (or maybe locally connected smartphone devices etc).
/// 
/// One could conceive of a gateway node that sends data about all other nodes out 
/// on an internet connection for more widespread visibility of node positions, 
/// say to a remote command post etc.
/// 
/// Note that each node has no specific routing or connectivity knowledge, and
/// each node has no idea if or how well it is connected to the rest of the
/// network or even if it is connected at all. So if a node goes out of range of
/// all the others, it wont 'know' that until its data gets stale. 
/// 
/// Caution: There are performance limitations:
/// 
/// Each message (with ID, timestamp, GPS position, altitude, course, speed etc)
/// is 27 octets of payload data. At 2000 bps this is a maximum possible air rate
/// of only 8 messages per second, and perhaps, realistically (after accounting
/// for collisions etc) 5 per second. This means that if there are many nodes
/// within radio listening range of each other, each node has to severely
/// throttle its broadcast rate. (On the plus side, if there are many nodes near
/// each other the need to rebroadcast positions is less important, so maybe it
/// balances out, since the nodes throttle their broadcast rate based on how busy
/// the channel is)
/// 
/// Operation depends on each node being within range of at least one other node,
/// which may be difficult with low power radios in wooded or hilly
/// terrain. Similarly with GPS reception which can be poor in heavily wooded
/// areas.
///
/// \par Software organisation
/// 
/// The example sketch requires the following additional software components:
/// 
/// - TinyGPS       http://arduiniana.org/libraries/tinygps/
/// - RF22          http://www.open.com.au/mikem/arduino/RF22
/// - GPSNet        This library
/// 
/// GPSNet is the main class. It is responsible for holding GPS reports, and
/// transmitting periodic updates to other nodes.  GPSNet class is generic in the
/// sense it can be made to work with any type of GPS receiver and and type of
/// radio transceiver. The example sketch provides the glue between GPSNet and the
/// GPS and Radio.
/// 
/// The example sketch uses TinyGPS to receive and decode NMEA sentences from the
/// GPS receiver, and to give GPS reports of the position of the local node to
/// GPSNet. It also uses RF22 to receive broadcast reports from other nodes and
/// also give them to GPSNet.
/// 
/// Periodically, GPSNet use an external callback function in the sketch to
/// broadcast a report to other nodes using RF22.
/// 
/// \par How to connect up your hardware
/// 
/// The supplied sketch works with an Arduino Mega. Mega is required for:
/// - Large SRAM of 8kb, allowing a large number of nodes to be stored in memory
/// - More than 1 hardware serial port, required for reliable GPS connection.
/// 
/// The default configuration of the sketch is for
/// 
/// Serial1 (Arduino RX1 pin D19 hardware serial port) is connected to the TX pin
/// of the GPS. GPS is configured for 4800 baud 8N1 (though this can be changed by
/// editing the sketch.
/// 
/// Serial (Arduino pins D0 and D1 hardware serial) is connected (as is usual) to
/// the standard Arduino USB-Serial port. Configuration commands can be sent to
/// and position updates can be received from the Arduino over this USB-Serial
/// connection. See below.
/// 
/// Pins D2, D50, D51, D52, D53 connected to the RF22 transceiver as described in
/// the documentation of the Arduino RF22
/// library. http://www.open.com.au/mikem/arduino/RF22 
/// 
/// Caution: IO level shifters are required between the Arduino and the RF22 to
/// accommodate the 3.3V RF22 module.
/// 
/// This software is Copyright (C) 2011 Mike McCauley. Use is subject to license
/// conditions. The main licensing options available are GPL V2 or Commercial:
/// 
/// \par GPSNetViewer
///
/// This is a simple Qt program that displays all the node positions received by a GPSNet node
/// on a Google Map. Download from http://www.airspayce.com/mikem/GPSNetViewer/gpsnetviewer1.0.tar.gz 
///
/// Sample screenshot at http://www.airspayce.com/mikem/GPSNetViewer/snapshot3.png
///
/// Requires Qt, QtCreator and the qextserialport library from http://code.google.com/p/qextserialport/
/// Runs on Windows, Linux and Mac.
/// After building the program with something like:
/// \code
/// tar zxvf gpsnetviewer1.0.tar.gz  
/// cd gpsnetviewer1.0
/// qmake
/// make
/// Connect an arduino running the gpsnet.ino sketch to your host
/// then run it with
/// ./qpsnetviewer
/// Select File->Configure
/// choose the serial port the Arduino gpsnet.ino sketch is connected to
/// OK.
/// See the "GPSNet Connected" go green, the received nodes shown in the right hand list and plottted 
/// on the map. Select 'Follow Me' to centre the map on postion of the conencted GPSNet node.
/// \endcode
///
/// \par Open Source Licensing GPL V2
///
/// This is the appropriate option if you want to share the source code of your
/// application with everyone you distribute it to, and you also want to give them
/// the right to share who uses it. If you wish to use this software under Open
/// Source Licensing, you must contribute all your source code to the open source
/// community in accordance with the GPL Version 2 when your application is
/// distributed. See http://www.gnu.org/copyleft/gpl.html
/// 
/// \par Commercial Licensing
///
/// This is the appropriate option if you are creating proprietary applications
/// and you are not prepared to distribute and share the source code of your
/// application. Contact info@airspayce.com for details.
///
/// \par Revision History
///
/// \version 1.0 Initial release
/// \version 1.1 Added README and Doxygen documentation of all classes
/// \version 1.2 LICENSE and first public release
/// \version 1.3 Improvements to example sketch serial interface to make it easier to parse 
///              outputs: prints "\nGPSNet\n" when it starts; 
///              All node reports are preficed by "Report:"
/// \version 1.4 Added GPSNetViewer description and instructions
/// \version 1.5 Fixed broken link to distribution
/// \version 1.6 Fixed broken link to distribution

#ifndef GPSNet_h
#define GPSNet_h

#include <Arduino.h>

/// \brief Records all the relevant details of a GPS position report, plus some
/// utility functions for operating on them.
///
/// The id member contains the node ID of the node that originated this report.
/// Node IDs are expected to be unique across the network.
typedef struct GPSReport
{

/// \def GPSNET_REPORT_ID_LEN
/// The length of the node ID, in octets. All octets are significant
#define GPSNET_REPORT_ID_LEN 8

/// \def GPSNET_MAGIC_VERSION_1
/// Magic number and Version number to identify this as a GPSReport type 1
#define GPSNET_MAGIC_VERSION_1 0xa1

    /// Contructor.
    /// Clears all members to 0.
    GPSReport();

    /// Tests whether the report has a a given node ID
    /// Returns true if there is an exact match over all octets of the ID
    /// \param[in] id Pointer to array of GPSNET_REPORT_ID_LEN octets of identifier
    /// \return true if there is an exact match
    boolean hasId(uint8_t* id);

    /// Tests whether 2 GPSReports are identical in all respects
    /// \param[in] that Pointer to the other report to test against
    /// \return true if all members match exactly
    boolean isIdenticalTo(GPSReport* that);

    /// Tests whether 2 GPSReports are geographically close to each other,
    /// with specified margins.
    /// param[in] that Pointer to the other report to test against
    /// param[in] latlongError Allowable angular difference in latitude or longitude, in 1/100000ths of a 
    /// degree (1.1112m at the equator).
    /// param[in] altitudeError Allowable error in metres
    /// \return true if the latitudes, longitudes and altitudes of the 2 positions are within the specified margins
    /// of each other.
    boolean isCloseTo(GPSReport* that, uint32_t latlongError = 100, uint32_t altitudeError = 10);

    /// Tests whether the timestamp (date and time) of the other rport is later than 
    /// this one
    /// \param[in] that Pointer to the other report to test against
    /// \return true if the time or date is later
    boolean isLaterThan(GPSReport* that);

    /// Print details of the report
    /// to the Serial port
    void    print();

    uint8_t  magic;                ///< Magic number and version of this report format == GPSNET_MAGIC_VERSION_1
    uint8_t  id[GPSNET_REPORT_ID_LEN];///< Unique ID of the node originating the report
    uint32_t date;                 ///< Current date as an integer (yymmdd)
    uint32_t time;                 ///< Current time as an integer (hhmmss)
    int32_t  latitude;             ///< Current latitude in 100000ths of a degree
    int32_t  longitude;            ///< Current longitude in 100000ths of a degree
    int16_t  altitude;             ///< Current altitude in m
    uint16_t speed;                ///< Current speed in knot
    uint16_t course;               ///< Current course in degrees
    uint8_t  flags;                ///< GPSnet internal flags (not used at present)
    uint8_t  status;               ///< External application specific status flags
    uint8_t  hops;                 ///< Num of radio hops from originator, 0 at originator
} GPSReport;


#define GPSNET_NUM_REPORTS 10

/////////////////////////////////////////////////////////////////////
/// \class GPSNet GPSNet.h <GPSNet.h>
/// \brief Manage reception, storage and update transmission of GPSReports
///
/// GPSNet implements a radio broadcast mesh
/// network among a number of GPS+radio equipped nodes, such that all nodes in the
/// network know the GPS position of all other nodes.
class GPSNet
{

/// \def GPSNET_STATISTICS_WINDOW_SECS
/// Size of the reception rate moving window in seconds, used to calculate
/// the average report reception rate
#define GPSNET_STATISTICS_WINDOW_SECS 60

/// \def GPSNET_TRANSMIT_TIME_JITTER
/// Amount of random jitter to add to transmit timer, in ms. Used to 
/// randomly vary the transmit time, to minimise recurring transmission collisions.
#define GPSNET_TRANSMIT_TIME_JITTER 1000

    /// \brief A doubly linked list of GPSReports for internal use by GPSNet
    /// Allows GPSReport array to be acessed by a doubly linked list
    /// linked in order of scheduled update transmissions
    /// For internal use by GPSNet only
    typedef struct GPSReportList
    {
        uint8_t   prev; ///< Index of the previous report
        uint8_t   next; ///< Index of the next report
        GPSReport report; ///< The report
    } GPSReportList;


public:

    /// Constructor
    /// Intialises most members to 0
    GPSNet();

    /// Tells GPSNet about a new report from the local GPS
    /// You should only call this when there is a new position report 
    /// that is significantly different from the previous position. 
    /// See GPSReport::isCloseTo() for assistance)
    /// \param[in] report Pointer to the new report
    void          newReport(GPSReport* report);

    /// Tells GPSNet about a new report received by radio from a remote node.
    /// Reports entered this way are used to update the reception rate statistics.
    /// \param[in] report Pointer to the report
    void          receivedReport(GPSReport* report);

    /// The number of currently known node reports
    /// \return The number of currently known node reports
    uint8_t       numReports();

    /// Fetch a report with a given node ID, and optionally its index
    /// \param[in] id Pointer to the node ID to match
    /// \param[in,out] index If index is not NULL it points to a uint8_t that is to be set to
    ///  the index of the matching node (if found)
    /// \return Pointer to the matching report if found, else NULL
    GPSReport*    reportWithId(uint8_t* id, uint8_t* index = NULL);

    /// Fetch the Report with the given index
    /// \param[in] index The index of the report inthe GPSNet report list
    /// \return Pointer to the Report at that index, if present, else NULL
    GPSReport*    reportWithIndex(uint8_t index);

    /// Prints a basic ASCII dump of all
    /// current reports to the Serial port
    void          printReports();

    /// Do the internal work of the GPSNet node
    /// You \b must call this frequently and often, but at least once a second.
    /// It is recomended that this be called in the idle loop of the main sketch.
    /// The transmitFunction may be called from within poll().
    void          poll();

    /// Tells GPSNet which function to call to broadcast an update report.
    /// The calling sketch should implement the transmitFunction in terms of its local
    /// radio interface
    /// \param[in] transmitFunction Pointer to a function to call when an update is to be transmitted.
    /// The function will be passed a pointer to this instance of GPSNet and the GPSReport to transmit
    void          setTransmitFunction(void (*transmitFunction)(GPSNet* net, GPSReport* report));

protected:

    /// Unlink a report from the report list
    /// Disconnects the report from the doubly linked list of reports in _reports
    /// \param[in] index Index of th report to unlink
    void          unlinkReportWithIndex(uint8_t index);

    /// Link a report into the report list
    /// Connects the report from the doubly linked list of reports in _reports
    /// so it apears after the report whose index is given as after
    /// param[in] index The index of the report to link in
    /// param[in]after the index of the report it is to appear after
    void          linkReportWithIndexAfterIndex(uint8_t index, uint8_t after);

    /// Schedules a report in the _reports list for the next update transmission
    /// It does this by moving it to the beginning of the linked list after the one indicated by 
    /// _lastUpdatedReportIndex
    void          scheduleReportForUpdate(uint8_t index);

    /// Transmits the next report scheduled for update.
    /// Calls transmitUpdate() and passes it the next report.
    /// Updates  _lastUpdatedReportIndex to indicate the recently transmitted report
    void          transmitNextUpdate();

    /// Transmit an update.
    /// Caller can override this funciton, or else can set a callback function
    /// with setTransmitFunction()
    /// \param[in] report The report to be transmitted
    virtual void  transmitUpdate(GPSReport* report);

    /// Recalculate _updateTransmitInterval
    /// Based on the average of the recent message arrival rate, with a moving window
    /// over a time period given by GPSNET_STATISTICS_WINDOW_SECS.
    void          evaluateReceptionRate();

    /// Execute various housekeeping tasks 
    /// required to be done once per second. Called automatically by poll() once per second.
    void          perSecondTasks();

private:
    /// If not NULL, this specifies a function to call whemn a report is to be 
    /// transmitted
    void          (*_transmitFunction)(GPSNet* net, GPSReport* report);

    uint32_t      _lastSecond;                  // millis

    uint32_t      _updateTransmitInterval;      // ms between update transmit times
    uint32_t      _lastUpdateTransmitTime;      // millis

    uint8_t       _receivedReportsInLastSecond; // Number of reports received in last second
    float         _receptionRate;

    uint8_t       _numReports;                  // Number of reports in _reports
    uint8_t       _lastUpdatedReportIndex;      // Index of the next report to transmit
    GPSReportList _reports[GPSNET_NUM_REPORTS]; // All the GPS reports we know about in update sequence
};

/// @example gpsnet.ino
/// Arduino sketch to provide a node on a GPSnet broadcast network to communicate 
/// GPS positions of all nodes throughout the network. 
/// Uses RF22 radios to preiodically broadcast GPS data
/// to nearby nodes, who in turn broadcast to nodes near them etc. 
///
/// Includes serial GPS interface, RF22 radio interface and USB-serial 
/// interface for configuration and emitting position reports. 
/// Saves configuration to EEPROM
/// You can use this with the PC based viewer program GPSNetViewer discussed in the main
/// documentation.


#endif