2010/08/28 by Rahul Urgaonkar, Urgaonkar, Rahul, Michael J. Neely +1
Computer Science · Engineering · #Advanced Wireless Network Optimization #Cooperative Communication and Network Coding #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1008.4896
openalex publication_date 2010/08/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate optimal routing and scheduling strategies for multi-hop\nwireless networks with rateless codes. Rateless codes allow each node of the\nnetwork to accumulate mutual information from every packet transmission. This\nenables a significant performance gain over conventional shortest path routing.\nFurther, it outperforms cooperative communication techniques that are based on\nenergy accumulation. However, it requires complex and combinatorial networking\ndecisions concerning which nodes participate in transmission, and which decode\nordering to use. We formulate three problems of interest in this setting: (i)\nminimum delay routing, (ii) minimum energy routing subject to delay constraint,\nand (iii) minimum delay broadcast. All of these are hard combinatorial\noptimization problems and we make use of several structural properties of their\noptimal solutions to simplify the problems and derive optimal greedy\nalgorithms. Although the reduced problems still have exponential complexity,\nunlike prior works on such problems, our greedy algorithms are simple to use\nand do not require solving any linear programs. Further, using the insight\nobtained from the optimal solution to a line network, we propose two simple\nheuristics that can be implemented in polynomial time and in a distributed\nfashion and compare them with the optimal solution. Simulations suggest that\nboth heuristics perform very close to the optimal solution over random network\ntopologies.\n