Optimal flow routing in multi-hop sensor networks with real-time constraints through linear programming.

We have proposed an algorithm for optimal real-time routing in multi-hop communication networks for multi-source/multi-sink connection. The algorithm deals with various capacity constraints in terms of communication limits and real-time constraints expressed as deadline for each particular flow of data. The objective is to find the optimal routing in terms of energy consumption. The algorithm is based on a data flow model leading to Linear Programming formulation and therefore it ensures polynomial-time complexity. An extension handling simultaneous real-time and non real-time routing is added. An example of data collection from 100 nodes is presented and performance experiments illustrating time complexity in dependence on the number of nodes are given.