Taxonomy based multiple ant colony optimization approach for routing in mobile ad hoc networks
In one embodiment, an apparatus comprises route management logic. The logic is operable to send a plurality of forward-route packets over a route to a destination node in a mobile ad hoc network. Each one of the plurality of forward-route packets is assigned to a different class of a plurality of classes. While traversing the route to the destination node, a forward-route packet accumulates a network metric that is associated with that class of the plurality of classes to which the forward-route packet is assigned. The logic is operable to receive from the destination node a plurality of backward-route packets. Each of the plurality of backward-route packets corresponds to one of the plurality of forward-route packets, and includes a network metric that is accumulated by the corresponding forward-route packet. The logic is operable to retrieve the network metrics from each of the plurality of backward-route packets and, based on the retrieved network metrics, to compute and store a probability value that is associated with the route to the destination node.
1. An apparatus comprising:
one or more processors; and
route management logic encoded in one or more tangible media for execution and when executed operable to:
send a first plurality of forward-route packets over a first route to a destination node in a mobile ad hoc network;
wherein each one of the first plurality of forward-route packets is assigned to a different class of a plurality of classes;
wherein, while traversing the first route to the destination node, a particular forward-route packet of the first plurality of forward-route packets accumulates a particular network metric that is associated with a particular class, of the plurality of classes, to which the particular forward-route packet is assigned;
receive, from the destination node, a first plurality of backward-route packets wherein each of the first plurality of backward-route packets corresponds to one of the first plurality of forward-route packets;
wherein a particular backward-route packet of the first plurality of backward-route packets includes a network metric that is accumulated by a corresponding forward-route packet of the first plurality of forward-route packets;
retrieve, in a first set of network metrics, each network metric that is included in each of the first plurality of backward-route packets; and
based on the first set of network metrics, compute and store a first probability value that is associated with the first route to the destination node.
2. The apparatus of claim 1 , wherein the route management logic further is operable to:
send a second plurality of forward-route packets over a second route to the destination node in the mobile ad hoc network;
wherein each one of the second plurality of forward-route packets is assigned to a different class of the plurality of classes;
wherein, while traversing the second route to the destination node, a particular forward-route packet of the second plurality of forward-route packets accumulates the particular network metric that is associated with the particular class, of the plurality of classes, to which the particular forward-route packet is assigned;
receive, from the destination node, a second plurality of backward-route packets wherein each of the second plurality of backward-route packets corresponds to one of the second plurality of forward-route packets;
wherein a particular backward-route packet of the second plurality of backward-route packets includes the network metric that is accumulated by a corresponding forward-route packet of the second plurality of forward-route packets;
retrieve, in a second set of network metrics, each network metric that is included in each of the second plurality of backward-route packets; and
based on the second set of network metrics, compute and store a second probability value that is associated with the second route to the destination node.
3. The apparatus of claim 2 , further comprising:
a plurality of network interfaces that are operable to communicatively connect to a plurality of nodes in the mobile ad hoc network; and
forwarding logic coupled to the plurality of network interfaces and when executed operable to:
receive a data packet on a first network interface of the plurality of network interfaces;
determine that the data packet is destined to the destination node in the mobile ad hoc network;
based on the first probability value and the second probability value, select one of the first route and the second route to the destination node; and
forward the data packet over the selected route to the destination node on a second network interface of the plurality of network interfaces.
4. The apparatus of claim 1 , wherein the route management logic further is operable to:
receive, from another node, a specific forward-route packet that is destined to a specific destination;
determine a specific class, of the plurality of classes, that is assigned to the specific forward-route packet;
update a specific network metric, associated with the specific class, that is stored in the specific forward-route packet; and
cause the specific forward-route packet to be sent to the specific destination.
5. The apparatus of claim 1 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a bandwidth metric which is associated with a network bandwidth class of the plurality of classes.
6. The apparatus of claim 1 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a path length metric which is associated with a network path length class of the plurality of classes.
7. The apparatus of claim 1 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a contention metric which is associated with a network contention class of the plurality of classes.
8. The apparatus of claim 1 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a reliability metric which is associated with a network reliability class of the plurality of classes.
9. The apparatus of claim 1 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a load metric which is associated with a network load class of the plurality of classes.
10. The apparatus of claim 1 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a communication cost metric which is associated with a network communication cost class of the plurality of classes.
11. The apparatus of claim 1 comprising one of a wireless switch and a wireless router in which the route management logic is installed.
12. The apparatus of claim 1 comprising a wireless device in which the route management logic is installed, wherein the wireless device is any one of:
a laptop computer;
a mobile telephone;
a Personal Digital Assistant (PDA); and
a node in a sensor network.
13. A computer-readable volatile or non-volatile storage medium storing logic which, when executed, is operable to:
send a first plurality of forward-route packets over a first route to a destination node in a mobile ad hoc network;
wherein each one of the first plurality of forward-route packets is assigned to a different class of a plurality of classes;
wherein, while traversing the first route to the destination node, a particular forward-route packet of the first plurality of forward-route packets accumulates a particular network metric that is associated with a particular class, of the plurality of classes, to which the particular forward-route packet is assigned;
receive, from the destination node, a first plurality of backward-route packets wherein each of the first plurality of backward-route packets corresponds to one of the first plurality of forward-route packets;
wherein a particular backward-route packet of the first plurality of backward-route packets includes a network metric that is accumulated by a corresponding forward-route packet of the first plurality of forward-route packets;
retrieve, in a first set of network metrics, each network metric that is included in each of the first plurality of backward-route packets; and
based on the first set of network metrics, compute and store a first probability value that is associated with the first route to the destination node.
14. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the logic when executed further is operable to:
send a second plurality of forward-route packets over a second route to the destination node in the mobile ad hoc network;
wherein each one of the second plurality of forward-route packets is assigned to a different class of the plurality of classes;
wherein, while traversing the second route to the destination node, a particular forward-route packet of the second plurality of forward-route packets accumulates the particular network metric that is associated with the particular class, of the plurality of classes, to which the particular forward-route packet is assigned;
receive, from the destination node, a second plurality of backward-route packets wherein each of the second plurality of backward-route packets corresponds to one of the second plurality of forward-route packets;
wherein a particular backward-route packet of the second plurality of backward-route packets includes the network metric that is accumulated by a corresponding forward-route packet of the second plurality of forward-route packets;
retrieve, in a second set of network metrics, each network metric that is included in each of the second plurality of backward-route packets; and
based on the second set of network metrics, compute and store a second probability value that is associated with the second route to the destination node.
15. The computer-readable volatile or non-volatile storage medium of claim 14 , further comprising forwarding logic coupled to a plurality of network interfaces and when executed operable to:
receive a data packet on a first network interface of the plurality of network interfaces;
determine that the data packet is destined to the destination node in the mobile ad hoc network;
based on the first probability value and the second probability value, select one of the first route and the second route to the destination node; and
forward the data packet over the selected route to the destination node on a second network interface of the plurality of network interfaces.
16. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the logic when executed further is operable to:
receive, from another node, a specific forward-route packet that is destined to a specific destination;
determine a specific class, of the plurality of classes, that is assigned to the specific forward-route packet;
update a specific network metric, associated with the specific class, that is stored in the specific forward-route packet; and
cause the specific forward-route packet to be sent to the specific destination.
17. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a bandwidth metric which is associated with a network bandwidth class of the plurality of classes.
18. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a path length metric which is associated with a network path length class of the plurality of classes.
19. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a contention metric which is associated with a network contention class of the plurality of classes.
20. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a reliability metric which is associated with a network reliability class of the plurality of classes.
21. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a load metric which is associated with a network load class of the plurality of classes.
22. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the first plurality of forward-route packets includes a forward-route packet that is configured to accumulate a communication cost metric which is associated with a network communication cost class of the plurality of classes.
23. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the logic is installable in any one of a wireless switch and a wireless router.
24. The computer-readable volatile or non-volatile storage medium of claim 13 , wherein the logic is installable in a wireless device, wherein the wireless device is any one of:
a laptop computer;
a mobile telephone;
a Personal Digital Assistant (PDA); and
a node in a sensor network.
25. An apparatus comprising:
means for sending a first plurality of forward-route packets over a first route to a destination node in a mobile ad hoc network;
wherein each one of the first plurality of forward-route packets is assigned to a different class of a plurality of classes;
wherein, while traversing the first route to the destination node, a particular forward-route packet of the first plurality of forward-route packets accumulates a particular network metric that is associated with a particular class, of the plurality of classes, to which the particular forward-route packet is assigned;
means for receiving, from the destination node, a first plurality of backward-route packets wherein each of the first plurality of backward-route packets corresponds to one of the first plurality of forward-route packets;
wherein a particular backward-route packet of the first plurality of backward-route packets includes a network metric that is accumulated by a corresponding forward-route packet of the first plurality of forward-route packets;
means for retrieving, in a first set of network metrics, each network metric that is included in each of the first plurality of backward-route packets; and
means for computing and storing, based on the first set of network metrics, a first probability value that is associated with the first route to the destination node.
26. A computer-implemented method for establishing routes in a mobile ad hoc network, the method comprising:
sending a first plurality of forward-route packets over a first route to a destination node in the mobile ad hoc network;
wherein each one of the first plurality of forward-route packets is assigned to a different class of a plurality of classes;
wherein, while traversing the first route to the destination node, a particular forward-route packet of the first plurality of forward-route packets accumulates a particular network metric that is associated with a particular class, of the plurality of classes, to which the particular forward-route packet is assigned;
receiving, from the destination node, a first plurality of backward-route packets wherein each of the first plurality of backward-route packets corresponds to one of the first plurality of forward-route packets;
wherein a particular backward-route packet of the first plurality of backward-route packets includes a network metric that is accumulated by a corresponding forward-route packet of the first plurality of forward-route packets;
retrieving, in a first set of network metrics, each network metric that is included in each of the first plurality of backward-route packets; and
based on the first set of network metrics, computing and storing a first probability value that is associated with the first route to the destination node;
wherein the method is performed by one or more devices.