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

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

Title : Path Optimization and Trusted Routing in MANET: An Interplay Between Ordered Semirings
Authors :
Baras, John S.
Somasundaram, Kiran K

Conference : The Second International Conference on Networks & Communications (NetCoM - 2010) pp. 88-98
Date: December 27 - December 29, 2010

In this paper, we formulate the problem of trusted routing as a transaction of services over a complex networked environment. We present definitions from service-oriented environments that unambiguously capture the difference between trust and reputation relations. We show that the trustworthiness measures associated with these relations have a linear order embedded in them. Identifying this order structure permits us to treat the trusted routing problem as a bi-objective path optimization problem. We consider bottleneck trust and present polynomial time solutions to obtain the optimal routing paths in various bi-objective settings. In developing these algorithms, we identify an interesting decomposition principle for (min,+) and (min,max) semirings, which yields a distributed solution.

Download Full Paper