create a connected graph

[Francisco Eduardo Balart Sanchez]

Good day:

I'm at my half-way Eng.hD, i'm working on a paper in which i implement a cluster-based algorithm as MAC

in order to test the performance i need to simulate it on NS3 which im almost done.

The problem:

• Create a connected graph

What i found so far:

• Reviewed similar threads
• https://groups.google.com/d/topic/ns-3-users/x9_JNrSyesw/discussion
• https://groups.google.com/d/topic/ns-3-users/bOv4xwi3U8A/discussion
  
• Current pointers:
• The watts strogatz graph algorithm have came up several time, so i'm trying to see if there is a similar implementation so i just port it.

At the end my main goal is to generate a connected graph in which i generate x and y positions to achieve this given the current NS3 libraries,

right now i'm reviewing if this is possible using

• GridpossitionAllocator
• Random and Uniform discpositionallocator

Thanks in advance and best regards

[Francisco Eduardo Balart Sanchez]

In the mean while i  made this brute force pseudo algorithm, works more less good, sometimes it skips a couple o nodes, hope somebody can provide me a hint here...

Basically i use the propagation model of Range, the algorithm generates coordinates such as 

1. they are not repeated
2. they make the node connected with at least a percentage of the total number of nodes

#define numOfNodes  30

#define numOfNodesDouble (double) numOfNodes

#define max_x 100.0

#define max_y 100.0

#define distance 15.0

#define percentage 20.0

#define percentageComp numOfNodesDouble*percentage/100

// 1- STEP 1: Generate RANDOM POSITIONS FOR THE NODES

  double x = 0.0;

  double y = 0.0;

  for(int i = 0; i < numOfNodes; i++)

  {

    x = ((double) rand() / (RAND_MAX))*max_x;

    y = ((double) rand() / (RAND_MAX))*max_y;

    positionAlloc->Add (Vector (x, y, 10.0));

  }

  mobility.SetPositionAllocator (positionAlloc);

  mobility.SetMobilityModel ("ns3::ConstantPositionMobilityModel");

  //mobility.SetMobilityModel ("ns3::RandomWalk2dMobilityModel","Bounds", RectangleValue (Rectangle (0, 1000, 0, 1000)));

  mobility.Install (nodes);

  

  int ii = 0;

  int jj = 0;

  double connectionsCounter = 0.0;

  double euclideanDistance = 0.0;

  // 2- STEP 2 ITERATE THROUGH EACH NODE POSITION

  for (NodeContainer::Iterator i = nodes.Begin (); i != nodes.End (); ++i)

  {

    Ptr<Node> nodePtr = *i;

    Ptr<MobilityModel> mob = nodePtr->GetObject<MobilityModel> (); 

    Vector pos = mob->GetPosition ();

    jj = 0;

    connectionsCounter = 0.0;

    for (NodeContainer::Iterator j = nodes.Begin (); j != nodes.End (); ++j)

    { // NOT ITERATE ON SAME NODE

      if(ii != jj)

      {

        Ptr<Node> nodePtrTwo = *j;

        Ptr<MobilityModel> mobTwo = nodePtrTwo->GetObject<MobilityModel> ();

        Vector posTwo = mobTwo->GetPosition ();

        euclideanDistance = sqrt(abs(pos.x - posTwo.x)*abs(pos.x - posTwo.x) + abs(pos.y - posTwo.y)*abs(pos.y - posTwo.y));

        if(euclideanDistance <= distance)

        {

          connectionsCounter++;

        } // 3- STEP 3 CHECK THE POSITION IS NOT REPEATED

        if((pos.x == posTwo.x) || (pos.y == posTwo.y))

        {

          NS_LOG_UNCOND("REPEATED POSITION  ");

          mob->SetPosition(Vector(((double) rand() / (RAND_MAX))*max_x, ((double) rand() / (RAND_MAX))*max_y, 10.0));

          ii = 0;

          jj = 0;

          i = nodes.Begin ();

          connectionsCounter = 0.0;

          break;

        }

        if(jj == (numOfNodes-1))

        { // 4- STEP 4 CHECK NODE CONNECTS AT LEAST WITH SPECIFIED % OF WHOLE GRAPH

          NS_LOG_UNCOND("Reached end of iterator "<<jj);

          if(connectionsCounter < percentageComp)

          {

            mob->SetPosition(Vector(((double) rand() / (RAND_MAX))*max_x, ((double) rand() / (RAND_MAX))*max_y, 10.0));

            ii = 0;

            jj = 0;

            i = nodes.Begin ();

            connectionsCounter = 0.0;

            break;

          }

        }

      }

      jj++;

    }

    NS_LOG_UNCOND("percentagecomp "<<percentageComp<<" connections "<<connectionsCounter);

    ii++;

  } 

[Francisco Eduardo Balart Sanchez]

I changed the code, remove the counters which were unnecessary now the first loop is from the end to beginning and second from beginning to end still this make the last node not to be properly placed see updated code:

#define numOfNodes  30

#define numOfNodesDouble (double) numOfNodes

#define max_x 100.0

#define max_y 100.0

#define distance 15.0

#define percentage 20.0

#define percentageComp numOfNodesDouble*percentage/100

  // 1- STEP 1: Generate RANDOM POSITIONS FOR THE NODES

  double x = 0.0;

  double y = 0.0;

  for(int i = 0; i < numOfNodes; i++)

  {

    x = ((double) rand() / (RAND_MAX))*max_x;

    y = ((double) rand() / (RAND_MAX))*max_y;

    positionAlloc->Add (Vector (x, y, 10.0));

  }

  mobility.SetPositionAllocator (positionAlloc);

  mobility.SetMobilityModel ("ns3::ConstantPositionMobilityModel");

  //mobility.SetMobilityModel ("ns3::RandomWalk2dMobilityModel","Bounds", RectangleValue (Rectangle (0, 1000, 0, 1000)));

  mobility.Install (nodes);

  

  double connectionsCounter = 0.0;

  double euclideanDistance = 0.0;

  // 2- STEP 2 ITERATE THROUGH EACH NODE POSITION

  NodeContainer::Iterator i = nodes.End ();

  while(i != nodes.Begin ())

  {

    --i;

    Ptr<Node> nodePtr = *i;

    Ptr<MobilityModel> mob = nodePtr->GetObject<MobilityModel> (); 

    Vector pos = mob->GetPosition ();

    connectionsCounter = 0.0;

    for (NodeContainer::Iterator j = nodes.Begin (); j != nodes.End (); ++j)

    {

      Ptr<Node> nodePtrTwo = *j;

      Ptr<MobilityModel> mobTwo = nodePtrTwo->GetObject<MobilityModel> ();

      Vector posTwo = mobTwo->GetPosition ();

      // NOT ITERATE ON SAME NODE

      if(nodePtr->GetId() != nodePtrTwo->GetId())

      {

        euclideanDistance = sqrt(abs(pos.x - posTwo.x)*abs(pos.x - posTwo.x) + abs(pos.y - posTwo.y)*abs(pos.y - posTwo.y));

        if(euclideanDistance <= distance)

        {

          connectionsCounter++;

        } 

        // 3- STEP 3 CHECK THE POSITION IS NOT REPEATED

        if((pos.x == posTwo.x) || (pos.y == posTwo.y))

        {

          NS_LOG_UNCOND("REPEATED POSITION  ");

          mob->SetPosition(Vector(((double) rand() / (RAND_MAX))*max_x, ((double) rand() / (RAND_MAX))*max_y, 10.0));

          i = nodes.End ();

          connectionsCounter = 0.0;

          break;

        }

        if( nodePtrTwo->GetId() == (numOfNodes-1))

        { // 4- STEP 4 CHECK NODE CONNECTS AT LEAST WITH SPECIFIED % OF WHOLE GRAPH

          NS_LOG_UNCOND("Reached end of iterator ");

          if(connectionsCounter < percentageComp)

          {

            mob->SetPosition(Vector(((double) rand() / (RAND_MAX))*max_x, ((double) rand() / (RAND_MAX))*max_y, 10.0));

            i = nodes.End ();

            connectionsCounter = 0.0;

            break;

          }

        }

      }

    }

  } 

[jared...@gmail.com]

I'm not a networking guy so take these comments with a grain of salt.  

a) If you want to enforce a topology (i.e. some network connectivity), why not just place your nodes wherever and use a MatrixPropagationLossModel to dictate the connections directly?  

b) If you want to explore clustering in a statistical sense, then why not just randomly place nodes and measure the connectivity?  Doing enough experiments should get some spread of connectivity percentages.

Doing a gives you all the control you need to get your target metric.

Doing b allows you to just use the random positioning tools and propagation models as is.

Jared.

[Francisco Eduardo Balart Sanchez]

Good day Jared:

Thanks for the reply, option a is a necessity but the approach of the MatrixPropagationLossModel is not an option since the objective

is the statistical sense as you mentioned in b at the end i only require to generate positions un such that the generated graph is connected.

I have now two iterations of the approach im trying to do in the code shown above.

thanks and best regards