## 4 REEMR: Reliable Energy-Efficient Multi-Level Routing Algorithm
### Fuzzy Petri Net Based Multi-Hop Routing  
After the clusters are formed, cluster heads aggregate the data traffic and forward it to the base station through a multi-hop route. Consequently, energy efficient and robust multi-hop routes among cluster heads should be constructed. As cluster heads change frequently, in this paper, we use fuzzy Petri nets and the reasoning mechanism to propose a reliable multi-hop routing among cluster heads. In Figure 7, the network topology of cluster heads, where the node 10 represents a base station, is shown. According to the definition of FPN, a place \(p\) represents a cluster head, \(\alpha(p)\) denotes the truth degree of reliability, a transition \(t\) is set up between the neighboring cluster heads, and then places and their corresponding transitions are connected using arcs. One-way direction from the source node to the destination node is chosen, and then FPN model of the network topology is shown in Figure 8. The initial mark of \(p_{1}\) is 1.0. Certainty factor and threshold value of every transition in the FPN model evaluate the reliability between each neighboring cluster head. The higher the certainty factor, the more reliable the link between two cluster heads. If the degree of reliability \(\alpha(p_{i})\) of place \(p_{i}\) exceeds the corresponding threshold value \(f(t)\), the transition \(t\) will be fired, which means that cluster head \(p_{i}\) can communicate with the neighboring cluster head \(p_{j}\), \(\alpha(p_{j})=\alpha(p_{i})\times\mu(t)\). The threshold should be set according to the specific need. The higher the threshold, the less the links between the neighboring cluster heads. In this paper, to simplify the FPN model, all the thresholds of transitions are unified to be \(0.1\) and the certainty factor of transition \(t\) is defined as follows:  
\[\mu(t)=1-0.5\times\frac{d}{R} \tag{4}\]  
where \(d\) is the distance between two neighboring cluster heads, and \(R\) is the communication radius of cluster heads. According to Figure 8, when the cluster head \(p_{1}\) needs to communicate with the base station \(p_{10}\), a reliable route needs to be constructed. This problem can be solved by developing a fuzzy reasoning algorithm based on fuzzy Petri net model. Assume that the truth degree of the cluster head \(p_{1}\) is given. The places \(p_{1}\) and \(p_{10}\) are called the starting place and the goal place, respectively. If the truth degree  
Figure 8: FPN model of topology of cluster heads. Figure 7: Topology of cluster heads. of \(p_{1}\) is greater than the corresponding threshold of its transition, it will flood a route request (RREQ) packet to its IRS. Otherwise, it will not flood the RREQ for the reason that this route is not reliable for a short time, which reduces the control overhead and provides a more reliable route. If a cluster head receives a RREQ packet from its neighbor and it is not the goal place, it will record the neighbor ID and forward the packet to all of its neighbors. Therefore, after a while, some relay cluster heads will receive at least one RREQ packet sent from the starting place. If the RREQ packets arrive at the goal place \(p_{10}\), \(p_{10}\) chooses the route with the largest degree of reliability as its the most reliable route. Finally, \(p_{10}\) will reply a Reply packet of the most reliable route to the starting place \(p_{1}\). The Reply control packet travels along the reverse path of the RREQ packet. Then multi-hop route among places is constructed. The fuzzy reasoning algorithm can be expressed as a sprouting tree [20], where each leaf node is denoted as \((p_{k},\alpha(p_{k}))\). The proposed algorithm is presented as follows:  
```
INPUT: the truth degree \(\alpha(p_{s})\) of the proposition \(\beta(p_{s})\) for the starting place \(p_{s}\). OUTPUT: the truth degree \(\alpha(p_{j})\) of the proposition for the goal place.