// The purpose of this program is to illustrate use of the "NetGraphTemplate" // classes. (Note the "NetGraphTemplate" allows different graph subclasses to // be created with different metric properties. The "MyGraph" exaple here // assumes a non-negative "double" value metric for "link cost". #include "manetGraph.h" #include "protoSpace.h" // we use this for its bounding box iteration #include #include #include // for sprintf() #include // for rand(), srand() #include // for "isprint()" #include // for "sqrt()" // "FastReader" is handy class I use for doing // buffered (fast) reading of an input file. class FastReader { public: enum Result {OK, ERROR_, DONE, TIMEOUT}; FastReader(FILE* filePtr); FastReader::Result Read(char* buffer, unsigned int* len, double timeout = -1.0); FastReader::Result Readline(char* buffer, unsigned int* len, double timeout = -1.0); bool Seek(int offset); private: enum {BUFSIZE = 2048}; FILE* file_ptr; char savebuf[BUFSIZE]; char* saveptr; unsigned int savecount; }; // end class FastReader void Usage() { fprintf(stderr, "Usage: graphExample \n"); } const unsigned int MAX_LINE = 256; class MyNode; class MyInterface : public NetGraph::InterfaceTemplate { public: MyInterface(MyNode& theNode, const ProtoAddress& addr) : NetGraph::InterfaceTemplate(theNode, addr) {} MyInterface(MyNode& theNode) : NetGraph::InterfaceTemplate(theNode) {} }; // end class MyInterface class MyInterface; class MyNode : public NetGraph::NodeTemplate, public ProtoSpace::Node { public: MyNode(); ~MyNode(); // _MUST_ call init to create a default interface bool Init(const ProtoAddress& addr); unsigned int GetId() const; void SetRtrPriority(UINT8 value) {rtr_priority = value;} UINT8 GetRtrPriority() const {return rtr_priority;} void SetRelayStatus(bool state) {relay_status = state;} bool GetRelayStatus() const {return relay_status;} void SetVisited(bool state) {visited = state;} bool WasVisited() const {return visited;} void SetPosition(double xPos, double yPos) { ordinate[0] = xPos; ordinate[1] = yPos; } double GetOrdinateX() const {return ordinate[0];} double GetOrdinateY() const {return ordinate[1];} // ProtoSpace::Node required overrides unsigned int GetDimensions() const {return 2;} double GetOrdinate(unsigned int index) const {return (ordinate[index]);} const double* GetOrdinatePtr() const {return ordinate;} private: UINT8 rtr_priority; bool relay_status; bool visited; double ordinate[2]; // x,y coordinates }; // end class MyNode class MyGraph : public NetGraphTemplate {}; MyNode::MyNode() : rtr_priority(0) { ordinate[0] = ordinate[1] = 0.0; } MyNode::~MyNode() { } bool MyNode::Init(const ProtoAddress& addr) { MyGraph::Interface* iface = new MyGraph::Interface(*this, addr); if (NULL != iface) { return AppendInterface(*iface); } else { PLOG(PL_ERROR, "MyNode::Init() new MyGraph::Interface() error: %s\n", GetErrorString()); return false; } } // end MyNode::Init() unsigned int MyNode::GetId() const { MyGraph::Interface* iface = GetDefaultInterface(); if (NULL != iface) { UINT8* addrPtr = (UINT8*)(iface->GetAddress().GetRawHostAddress()); unsigned int id = addrPtr[2]; id = (id << 8) + addrPtr[3]; return id; } else { ASSERT(0); return ((unsigned int)-1); } } // end MyNode::GetId() const double RANGE_MAX = 300.0; inline double CalculateDistance(double x1, double y1, double x2,double y2) { double dx = x1 - x2; double dy = y1 - y2; return sqrt(dx*dx + dy*dy); } // end CalculateDistance() // This updates the "space" with data from the next time "epoch" double ReadNextEpoch(FastReader& reader, ProtoSpace& space, MyGraph& graph); // This updates the graph connectivity from the "space" and using "RANGE_MAX" comms range bool UpdateGraphFromSpace(MyGraph& graph, ProtoSpace& space, ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool); // This calculates an ECDS relay set given the "graph" int CalculateFullECDS(MyGraph& graph, MyGraph::Interface::SimpleList& relayList, ProtoGraph::Vertice::SortedList::ItemPool* sortedVerticeItemPool); // This calculates the nodal neighbor "density" of the given "graph" double CalculateDensity(MyGraph& graph); // Some "hacky" scaling factors to output a "GPS" version // (some other code needs to be uncommented, etc to use this) double X_MIN = -77.028633; double X_MAX = -77.021267; double X_SCALE = (X_MAX - X_MIN) / 1600.0; double Y_MIN = 38.828533; double Y_MAX = 38.822817; double Y_SCALE = (Y_MAX - Y_MIN) / 600.0; int main(int argc, char* argv[]) { // argv[1] is expected to be an ns-2 "mobility trace" file // (i.e. with "setdest" commands). This program uses the // "destinations" given from "setdest" commands to as node // positions. It does _not_ interpolate the "setdest" // locations itself. We will eventually create a more useful // version of this program (likely under a different name, etc) // that can use our more recently developed node location/motion // XML schema (See the NRL Mobile Network Modeling Tools). if (argc < 2) { Usage(); return -1; } // Create a MyGraph instance that we will populate // with nodes/interfaces from our "mobility trace file" MyGraph graph; // This is a pool of ProtoGraph::Vertice::SortedList::Items // that are used for temporary lists of MyGraph::Interfaces // as we adjust graph connectivity, etc. Note that the use of an // "external" item pool is _optional_ for the ProtoGraph/MyGraph // list classes, but can boost performance by reducing memory // alloc/deallocs when doing a lot of list manipulation. // If a list was inited with a "pool", then it is important to // keep the "pool" valid until after any associate "lists" are // destroyed as "pools" do _not_ keep track of which lists are // using them (yet!). ProtoGraph::Vertice::SortedList::ItemPool sortedVerticeItemPool; // We use the ProtoSpace to organize nodes by their position // and use the ProtoSpace bounding box iterator to efficiently // find adjacencies ProtoSpace space; // Open the trace file for reading FILE* infile = fopen(argv[1], "r"); if (NULL == infile) { perror("graphExample: fopen error"); return -1; } printf("bgbounds -100,-100,1500,500\n"); // Uncomment this for the "GPS" version //printf("bgbounds -77.028633,38.828533,-77.021267,38.822817\n"); double lastTime = -1.0; double nextTime; FastReader reader(infile); // "ReadNextEpoch" adds new "Nodes" to the "space" (and updates // the position of Nodes from prior epochs - the "graph" is provided // so that already existing "Nodes" can be found.) while (0.0 <= (nextTime = ReadNextEpoch(reader, space, graph))) { // Output "wait" command for SDT visualization, if applicable if (lastTime >= 0.0) printf("wait %f\n", (float)(1000.0 * (nextTime - lastTime))); lastTime = nextTime; // "UpdateGraphFromSpace()" adds/removes "links" between the Nodes depending // upon their spatial distance and the "RANGE_MAX" communications range // (TBD - pass the "comms range" as a parameter to this function?) TRACE("graphExample: Updating graph connections for time:%lf ..................................\n", nextTime); if (!UpdateGraphFromSpace(graph, space, &sortedVerticeItemPool)) { PLOG(PL_ERROR, "graphExample: error updating graph ...\n"); return -1; } TRACE("graphExample: Performing E-CDS relay set selection for time:%lf ===================================\n", nextTime); // "CalculateFullECDS" implements the ECDS relay set selection // algorithm, marking selected nodes using the MyNode::SetRelayStatus() // method. It also copies the selected nodes into the "relayList" // that is passed to it. (This is mainly for illustrative purposes // to demonstrate the utility of the MyGraph lists, iterators, etc MyGraph::Interface::SimpleList relayList; int relays = CalculateFullECDS(graph, relayList, &sortedVerticeItemPool); TRACE("relays is %d\n", relays); // Iterate over our relay set and color the relays "blue" and their // (non-relay) one-hop neighbors "green" // We also build up a "disconnectedList" by first putting all nodes // into it and then remove the relays and their one-hop neighbors. // The disconnected nodes remaining in the list are colored "red" // a) Initialize our "disconnectedList" with all ifaces in graph // (note we _could_ have used the "sortedVerticeItemPool" here as // well, but didn't to illustrate that it is optional. We // would perform better here if did use it, though. MyGraph::Interface::SortedList disconnectedList(&sortedVerticeItemPool); MyGraph::InterfaceIterator ifaceIterator(graph); MyGraph::Interface* iface; while (NULL != (iface = ifaceIterator.GetNextInterface())) disconnectedList.Insert(*iface); // b) Remove relays (and their neighbors) from the "disconnectedList" // and output appropriate node colors MyGraph::Interface::SimpleList::Iterator relayIterator(relayList); MyGraph::Interface* relayIface; while (NULL != (relayIface = relayIterator.GetNextInterface())) { // It's a relay, so remove from disconnected list if (NULL != disconnectedList.FindInterface(relayIface->GetAddress())) disconnectedList.Remove(*relayIface); MyNode& relayNode = relayIface->GetNode(); printf("node %d symbol circle,blue,3\n", relayNode.GetId()); MyGraph::AdjacencyIterator neighborIterator(*relayIface); MyGraph::Interface* neighborIface; while (NULL != (neighborIface = neighborIterator.GetNextAdjacency())) { // It's a relay neighbor, so remove from disconnected list if (NULL != disconnectedList.FindInterface(neighborIface->GetAddress())) disconnectedList.Remove(*neighborIface); MyNode& neighborNode = neighborIface->GetNode(); if (!neighborNode.GetRelayStatus()) printf("node %d symbol circle,green,3\n", neighborNode.GetId()); } } // c) Color any nodes remaining in "disconnectedList" red MyGraph::Interface::SortedList::Iterator dcIterator(disconnectedList); MyGraph::Interface* disconnectedIface; while (NULL != (disconnectedIface = dcIterator.GetNextInterface())) { MyNode& disconnectedNode =disconnectedIface->GetNode(); printf("node %d symbol circle,red,3\n", disconnectedNode.GetId()); } double nodedensity = 0; nodedensity = CalculateDensity(graph); TRACE("density is %f\n",nodedensity); } fprintf(stderr, "graphExample: Done.\n"); return 0; } // end main() double ReadNextEpoch(FastReader& reader, ProtoSpace& space, MyGraph& graph) { double lastTime = -1.0; // Read the "setdest" lines from the file, finding // new nodes and their x,y positions versus time // line format we want is ' at