What is Shortest path?

SHORTEST PATH

        An algorithm that is designed essentially to find a path of minimum length between two specified vertices of a connected weighted graph

·         Initialize the array smallest Weight so that smallest Weight[u] = weights[vertex, u].

·         Set smallest Weight[vertex] = 0.

·         Find the vertex, v, that is closest to vertex for which the shortest path has not been determined.

·         Mark v as the (next) vertex for which the smallest weight is found.

·         For each vertex w in G, such that the shortest path from vertex to w has not been determined and an edge (v, w) exists, if the weight of the path to w via v is smaller than its current weight, update the weight of w to the weight of v + the weight of the edge (v, w).

NS2 CODE FOR SHORTEST PATH ROUTING

DIJIKSTRA’S ROUTING ALGORITHM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

int main() { Node N0(0); Node N1(1); Node N2(2); Node N3(3); Node N4(4); RoutingVec_t NextHop; RoutingVec_t Parent;  N0.AddAdj(1, 10);  N0.AddAdj(2, 5);  N1.AddAdj(3, 1);  N1.AddAdj(2, 2);  N2.AddAdj(4, 2);  N2.AddAdj(1, 3);  N2.AddAdj(3, 9);  N3.AddAdj(4, 4);  N4.AddAdj(0, 7);  N4.AddAdj(3, 6);  Nodes.push_back(&N0);  Nodes.push_back(&N1);  Nodes.push_back(&N2);  Nodes.push_back(&N3);  Nodes.push_back(&N4);  for (nodeid_t i = 0; i < Nodes.size(); i++)    { // Get shortest path for each root node      printf("\nFrom root %ld\n", i);      Dijkstra(Nodes, i, NextHop, Parent);      PrintParents(Parent);      for (unsigned int k = 0; k < Nodes.size(); k++)        printf("Next hop for node %d is %ld\n", k, NextHop[k]);      printf("Printing paths\n");      for (nodeid_t j = 0; j < Nodes.size(); j++)        {          PrintRoute(i, j, Parent);        }    }  return(0); }

Different ways to identify shortest path routing in ns2

• Transmission and propagation delays.
• Queuing delays.
• Minimum number of hops.

The optimal path is obtained through three steps, which is reverse route calculation in route request (RREQ), reverse route calculation in route reply (RREP) and reverse route calculation in route error (RERR). Experiments have been carried out using network simulator (NS2) and the obtained results are performed better than reactive routing protocol (AODV).

CLICK HERE TO VIEW MORE DETAILS

What is Malicious node?

MALICIOUS NODE

Intrusion Detection Systems (IDS) in Mobile Ad hoc Networks (MANETs) are required to develop a strong security scheme it is therefore necessary to understand how malicious nodes can attack the MANETs. Focusing on the Optimized Link State Routing (OLSR) protocol, an IDS mechanism to accurately detect and isolate misbehavior node(s) in OLSR protocol based on End-to-End (E2E) communication between the source and the destination is proposed. The collaboration of a group of neighbor nodes is used to make accurate decisions. Creating and broadcasting attackers list to neighbor nodes enables other node to isolate misbehavior nodes by eliminating them from the routing table. Eliminating misbehavior node allows the source to select another trusted path to its destination.

ROUTING PROTOCOLS 

                         The routing protocols implemented in MANETs are globally classified into two categories: proactive or table driven protocols and reactive or on-demand protocols. Table driven protocols rely on a table, which maintains consistent up-to-date information concerning routes to all possible destinations, whereas on-demand routing protocols implement source-initiated route organization, where a route is created when desired by the node.

ATTACKS USING MODIFICATION

                           Modification is a type of attack when an authorized party not only gains access to but tampers with an asset. For example a malicious node can redirect the network traffic and conduct DOS attacks by modifying message fields or by forwarding routing message with false values.

ATTACKS USING IMPERSONATION

                         As there is no authentication of data packets in current ad-hoc network, a malicious node can launch many attacks in a network by masquerading as another node i.e. spoofing. Spoofing is occurred when a malicious node misrepresents its identity in the network (such as altering its MAC or IP address in outgoing packets) and alters the target of the networktopology that a benign node can either.

ATTACKS THROUGH FABRICATION

                        Fabrication is an attack in which an authorizedparty not only gains the access but also inserts counterfeit objects into the system. In MANET, fabrication is used to refer the attacks performed by generating false routing messages Gray hole attack We now describe the grayhole attack on MANETS. 

CLICK HERE TO VIEW MORE DETAILS

What are the Difference Between Algorithm and Heuristic?

DIFFERENCE BETWEEN ALGORITHM AND HEURISTIC

An algorithm is a set of well-defined instructions for carrying out a particular task. It must be sound and complete. That mean it must gives you the correct answer and it must works for all cases.Usually, an algorithm is predictable, deterministic, and not subject to chance. An algorithm tells you how to go from point A to point B with no detours, no side trips to points D, E, and F, and no stopping to smell the roses or have a cup of joe.

A heuristic is a technique that helps you look for an answer. Its results are subject to chance because a heuristic tells you only how to look, not what to find. It doesn’t tell you how to get directly from point A to point B; it might not even know where point A and point B are. In effect, a heuristic is an algorithm in a clown suit. It’s less predictable, it’s more fun, and it comes without a 30-day, money-back guarantee.

  

Here is an algorithm for driving to someone’s house: Take Highway 167 south to Puyallup. Take the South Hill Mall exit and drive 4.5 miles up the hill. Turn right at the light by the grocery store, and then take the first left. Turn into the driveway of the large tan house on the left, at 714 North Cedar.

Here’s a heuristic for getting to someone’s house: Find the last letter we mailed you. Drive to the town in the return address. When you get to town, ask someone where our house is. Everyone knows us—someone will be glad to help you. If you can’t find anyone, call us from a public phone, and we’ll come get you.

The difference between an algorithm and a heuristic is subtle, and the two terms overlap somewhat. The main difference between the two is the level of indirection from the solution. An algorithm gives you the instructions directly. A heuristic tells you how to discover the instructions for yourself, or at least where to look for them.

                                                CLICK HERE MORE DETAILS

How to calculate the Throughput Level in NS2?

THROUGHPUT

Following awk file will calculate the throughput with running time (throughput versus time).

The following code will count all the received application packets 

in a network such that we can calculated the network throughput. 

 If  a throughput of a specific node has to be calculated, then we can simply add the node_id in the if condition.

The code simply prints the observed throughput during the time_interval through out the simulation time. We can change the time_interval variable according to our requirements.

In the following code:

·         packet_size * recv * 8.0 gives the total number of bits received. Packet size is the size of packet used in Application layer.

·         diving the value by 1000 gives us the throughput in kbps.

#============== throughput.awk ================

BEGIN {
recv=0;
gotime = 1;
time = 0;
packet_size = 50;
time_interval=2;
}
#body
{
        event = $1
             time = $2
             node_id = $3
             level = $4
             pktType = $7

 if(time>gotime) {

  print gotime, (packet_size * recv * 8.0)/1000; #packet size * ... gives results in kbps
  gotime+= time_interval;
  recv=0;
  }

#========Calculate throughput==========

if (( event == "r") && ( pktType == "cbr" ) && ( level=="AGT" ))
{
 recv++;
}

} #body


END {
;
}

                                        

And finally the throughput level has to be calculated and the above graph diagram illustrates the output of the throughput calculation.

                                     CLICK HERE MORE DETAILS

What is Heuristic algorithm?

HEURISTIC ALGORITHM

The term heuristic is used for algorithms which find solutions among all possible ones ,but they do not guarantee that the best will be found,therefore they may be considered as approximately and not accurate algorithms.These algorithms,usually find a solution close to the best one and they find it fast and easily.Sometimes these algorithms can be accurate,that is they actually find the best solution, but the algorithm is still called heuristic until this best solution is proven to be the best.The method used from a heuristic algorithm is one of the known methods,such as greediness,but in order to be easy and fast the algorithm ignores or even suppresses some of the problem's demands.

Heuristic Search

A heuristic is a method that

• might not always find the best solution
• but it is guaranteed to find a good solution in reasonable time.

• By sacrificing completeness it increases efficiency.
• Useful in solving tough problems which
  • could not be solved any other way.
  • solutions take an infinite time or very long time to compute.

The classic example of heuristic search methods is the travelling salesman problem.

Heuristic Search methods Generate and Test Algorithm

1. generate a possible solution which can either be a point in the problem space or a path from the initial state.
2. test to see if this possible solution is a real solution by comparing the state reached with the set of goal states.
3. if it is a real solution, return. Otherwise repeat from 1.

This method is basically a depth first search as complete solutions must be created before testing. It is often called the British Museum method as it is like looking for an exhibit at random. A heuristic is needed to sharpen up the search. Consider the problem of four 6-sided cubes, and each side of the cube is painted in one of four colours. The four cubes are placed next to one another and the problem lies in arranging them so that the four available colours are displayed whichever way the 4 cubes are viewed. The problem can only be solved if there are at least four sides coloured in each colour and the number of options tested can be reduced using heuristics if the most popular colour is hidden by the adjacent cube.

Hill climbing

Here the generate and test method is augmented by an heuristic function which measures the closeness of the current state to the goal state.

1. Evaluate the initial state if it is goal state quit otherwise current state is initial state.
2. Select a new operator for this state and generate a new state.
3. Evaluate the new state
   • if it is closer to goal state than current state make it current state
   • if it is no better ignore
4. If the current state is goal state or no new operators available, quit. Otherwise repeat from 2.

In the case of the four cubes a suitable heuristic is the sum of the number of different colours on each of the four sides, and the goal state is 16 four on each side. The set of rules is simply choose a cube and rotate the cube through 90 degrees. The starting arrangement can either be specified or is at random.

CLICK HERE TO VIEW MORE DETAILS