Secure Overlay Routing for Large Scale Networks

Probabilistic key pre-distribution schemes have recently emerged as major tools of addressing secure routing challenge in wireless networks. In our previous work, we propose an algorithm capable of finding optimal secure paths in overlay wireless networks. An important concern related to that algorithm is the scalability of the solution for large scale networks containing thousands of nodes. In this paper, we propose two alternative solutions for the previously formulated problem of secure overlay routing that can effectively scale to thousands of nodes. The first one is a deterministic Dijkstra-based algorithm analytically proven to find the optimal path with a time complexity much lower than that of the original algorithm. The second alternative is an approximation method capable of finding a near optimal path with an accuracy of 99 percent compared to the optimal path. At the cost of a space complexity in the order O(n log(3)n), this algorithm can find the near optimal path with a linear time complexity compared to quadratic or multiplicative time complexity associated with the first algorithm proposed in this paper. Experimental results using a number of different key pre-distribution schemes confirm our analytical findings.