2017/09/05 by Arpan Chattopadhyay, Chattopadhyay, Arpan, Avishek Ghosh +3
Computer Science · Engineering · #Advanced MIMO Systems Optimization #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Wireless Networks and Protocols
paper · pdf · doi:10.48550/arxiv.1709.01566
openalex publication_date 2017/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We are motivated by the need for impromptu (or as-you-go) deployment of\nmultihop wireless networks, by human agents or robots; the agent moves along a\nline, makes wireless link quality measurements at regular intervals, and makes\non-line placement decisions using these measurements. As a first step, we have\nformulated such deployment along a line as a sequential decision problem. In\nour earlier work, we proposed two possible deployment approaches: (i) the pure\nas-you-go approach where the deployment agent can only move forward, and (ii)\nthe explore-forward approach where the deployment agent explores a few\nsuccessive steps and then selects the best relay placement location. The latter\nwas shown to provide better performance but at the expense of more measurements\nand deployment time, which makes explore-forward impractical for quick\ndeployment by an energy constrained agent such as a UAV. Further, the\ndeployment algorithm should not require prior knowledge of the parameters of\nthe wireless propagation model. In [1] we, therefore, developed learning\nalgorithms for the explore-forward approach.\n The current paper provides deploy-and-learn algorithms for the pure as-you-go\napproach. We formulate the sequential relay deployment problem as an average\ncost Markov decision process (MDP), which trades off among power consumption,\nlink outage probabilities, and the number of deployed relay nodes. First we\nshow structural results for the optimal policy. Next, by exploiting the special\nstructure of the optimality equation and by using the theory of asynchronous\nstochastic approximation, we develop two learning algorithms that\nasymptotically converge to the set of optimal policies as deployment\nprogresses. Numerical results show reasonably fast speed of convergence, and\nhence the model-free algorithms can be useful for practical, fast deployment of\nemergency wireless networks.\n