# A Family of ACO Routing Protocols for Mobile Ad Hoc Networks
## 4 AntOR Protocol Family
If a unicast control packet was being forwarded, a Unicast Link Notification (ULN) message is sent to the predecessor node. This process is repeated until we reach the source node. Finally, the third distinctive feature of HACOR with respect to its predecessor is the introduction of a variant of Simple Ant Colony Optimization (S-ACO) in the maintenance of established routes and the exploration of new routes phase, which basically consists of the following:  
1. The virtual pheromone leaves, as is necessary at this phase. 2. We do not utilize the evaporation process. 3. A free-loop method is used when the proactive forward ant (PFA) has come to the destination node. Subsequently the loop is removed, this PFA becoming a free-loop PBA, which returns to the source by the visited nodes in the list, updating the routing tables of each node. 4. We do not need the initial establishment of pheromone values to each one-hop neighbor. The exploration process is done hop-by-hop with the pheromone information that has the one-hop neighbors using the Hello messages. Each node that receives a Hello message from another one-hop neighbor updates its route with the new value of the pheromone. 5. The proactive forward ants utilize the link-disjoint route. 6. This use of the disjoint routes involves the checking of whether the one-hop neighbor that has to forward the corresponding proactive agent belongs to a disjoint route or not. In the case that the neighbor belongs to a disjoint route, it is not chosen (in order to reduce the overhead). As its name suggests, PAntOR [23] derives from AntOR, more specifically it can be considered a parallel approximation of AntOR-DNR. The reason for choosing AntOR-DNR (and not AntOR-DLR) is that it is intended to analyze the worst case, hence the choice of the first for being more restrictive. Previously to PAntOR's specification, it is advisable to point out some aspects of the parallelization of the ACO algorithms. Firstly, it should be known that practically all parallel work on ACO algorithms is designed for centralized systems based on the technique of master-slave, where the central master distributes work to other processors. PAntOR, on the other hand, is designed for decentralized systems, which gives it even greater relevance. Secondly, it is good to know that the parallel ACO algorithms are classified according to the two criteria described below:  
A possible classification difference exists if a parallelization of an ACO algorithm is standard or is especially designed. A standard ACO parallelization aims to decrease the run time without changing the behavior of the algorithm. On the contrary, specific parallel algorithms change ACO in order to obtain a more efficient algorithm. A method utilized to differentiate between these two approaches consists of how it makes use of the exchange of information between processors. Another possible classification checks if the algorithm has a centralized or decentralized approach. In a centralized approach, it is normal that a processor collects information of the pheromone, as well as the different solutions of other processors. Thus, the pheromone update is done in a central manner. In a decentralized approach, each processor has to calculate the pheromone update itself using the information received from other processors. PAntOR consists of a standard ACO parallelization (large-grained parallelization) with a decentralized approach. To understand how PAntOR works, it is necessary to employ three concepts:  
1. Process: program running. The processes are managed by the operating system. 2. Thread: the basic unit of execution. Any program that executes at least has a thread. 3. Portable Operating System Interface (POSIX) thread: Standard based on the threads Application Programming Interface (API) for C/C++. We use POSIX [24; 25] thread because it allows a new concurrent process flow to expand.