Path Optimization and Trusted Routing in MANET: An Interplay Between Ordered Semirings

In this paper, the authors formulate the problem of trusted routing as a transaction of services over a complex networked environment. They present definitions from service-oriented environments that unambiguously capture the difference between trust and reputation relations. They show that the trustworthiness metrics associated with these relations have a linear order embedded in them. Identifying this order structure permits one to treat the trusted routing problem as a bi-objective path optimization problem. They consider bottleneck trust and present polynomial time algorithms to obtain the optimal routing paths in various bi-objective settings.