DTMC analysis of connectedness for 2-dimension wireless relay placement with regular string topology

This paper has proposed to analyse the probability of connectedness in a 1-dimension string of N relays being placed in a regular topology. The proposed technique is based on the transient behaviour of time-homogeneous discrete-time Markov chain. And the computational complexity is O(r²log₂N), where r is the number of forwarding neighbors for each relay in the string. Further, in coping with realistic wireless relay placements spanning a geographical area, this paper has formulated the 2-dimension scenarios where the source station S, the destination station D and other stations are interconnected by independent relay strings. By using the inclusion-exclusion principle, the desired probability of S-D connectedness for 2-dimension case has been derived. Here, the resultant computational complexity is O(2^m), where m is the total number of paths between S and D. Finally, by combining both 1-dimension and 2-dimension analyses, numerical results have been given to demonstrate the applicability of obtainable mathematical formula herein derived.