Conditions for Product Form Solutions in Multihop Packet Radio Network Models.

摘要

Consider multihop packet radio networks operating under a general class of channel access protocols. For the purpose of throughput analysis, analytical models are considered which describe the joint activity of the transmitters in the network, under the assumptions of heavy traffic and zero propagation and processing delays. The problem addressed in this report is that of finding conditions for the existence of product form solutions for the steady-state probabilities of these models. The main result states that a necessary and sufficient conditions for a given network topology, channel access protocol, and traffic pattern, to lead to a product form solution is that the blocking between each pair of used links, as specified by the access protocol, by symmetric. This result assumes Poisson scheduling point processes associated with the links of the network. The proof is given in two steps: first, for systems where all packet length distributions are exponential, giving rise to Markovian processes; and second, for general packet length distributions (subject to the restriction of possessing a positive density almost everywhere), giving rise to Generalized Semi-Markov Processes. It is also shown that a product form solution does not exist whenever any of the scheduling point process in the network is not Poisson. In addition, it is proven that the computation of the normalization factor appearing in the expression of the product form solution is an NP-hard problem. (rh)