1Throughput Optimization inMobile Backbone NetworksEmily M. Craparo, Member, IEEE, Jonathan P. How, Senior Member, IEEE,and Eytan Modiano, Senior Member, IEEEAbstract—This paper describes new algorithms for throughput optimization in a mobile backbone network. This hierarchicalcommunication framework combines mobile backbone nodes, which have superior mobility and communication capability, withregular nodes, which are constrained in mobility and communication capability. An important quantity of interest in mobile backbonenetworks is the number of regular nodes that can be successfully assigned to mobile backbone nodes at a given throughput level.This paper develops a novel technique for maximizing this quantity in networks of fixed regular nodes using mixed-integer linearprogramming (MILP). The MILP-based algorithm provides a significant reduction in computation time compared to existing methodsand is computationally tractable for problems of moderate size. An approximation algorithm is also developed that is appropriate forlarge-scale problems. This paper presents a theoretical performance guarantee for the approximation algorithm and also demonstratesits empirical performance. Finally, the mobile backbone network problem is extended to include mobile regular nodes, and exact andapproximate solution algorithms are presented for this extension.Index Terms—Wireless sensor networks, mobile communication systems.F1 INTRODUCTIONDETECTION and monitoring of spatially distributed phe-nomena often necessitates the distribution of sensingplatforms. For example, multiple mobile robots can be used toexplore an area of interest more rapidly than a single mobilerobot [1], and multiple sensors can provide simultaneouscoverage of a relatively large area for an extended period oftime [2]. However, in many applications the data collected bythese distributed platforms is best utilized after it has beenaggregated, which requires communication among the roboticor sensing agents. This paper focuses on a hierarchical networkarchitecture called a mobile backbone network, in which mo-bile agents are deployed to provide long-term communicationsupport for other agents in the form of a fixed backbone overwhich end-to-end communication can take place. Mobile back-bone networks can be used to model a variety of multi-agentsystems. For example, a heterogeneous system composed ofair and ground vehicles conducting ground measurements ina cluttered environment can be appropriately modeled as amobile backbone network, as can a team of mobile roboticagents deployed to collect streams of data from a network ofstationary sensor nodes.Previous work has focused on optimal placement of mobilebackbone nodes in networks of fixed regular nodes, with theobjective of providing permanent communication supportfor the regular nodes [3]. Existing techniques, while exact,suffer from intractable computation times, even for problemsof modest size. Furthermore, mobility of regular nodes has• E. M. Craparo, J. P. How and E. Modiano are with the Departmentof Aeronautics and Astronautics, Massachusetts Institute of Technology,Cambridge, MA 02139.E-mail: [email protected] been adequately addressed. This paper provides tractablesolutions to the important problem of maximizing the numberof regular nodes that achieve a desired level of throughput. Italso describes a new mobile backbone network optimizationproblem formulation that models regular node mobility, andit provides tractable solutions to this problem, including thefirst known approximation algorithm with computation timethat is polynomial in both the number of regular nodes andthe number of mobile backbone nodes.2 BACKGROUND AND PROBLEM STATEMENTMobile backbone networks were described by Rubin et al.[4] and Xu et al. [5] as a solution to the scalability issuesinherent in mobile ad hoc networks. Noting that most commu-nication bandwidth in single-layer large-scale mobile networksis dedicated to packet-forwarding and routing overhead, theyproposed a multi-layer hierarchical network architecture, as iscurrently used in the Internet. Srinivas et al. [6] defined twotypes of nodes: regular nodes, which have limited mobility andcommunication capability, and mobile backbone nodes, whichhave greater communication capability than regular nodes andwhich can be placed at arbitrary locations in order to providecommunication support for the regular nodes.Srinivas et al. [6] formulated the connected disk cover(CDC) problem, in which many mobile backbone nodes withfixed communication ranges are deployed to provide commu-nication support for a set of fixed regular nodes. The goal ofthe CDC problem is to place the minimum number of mobilebackbone nodes such that each regular node is covered byat least one mobile backbone node and all mobile backbonenodes are connected to each other. Thus, the CDC problemtakes a discrete approach to modeling communication, in thattwo nodes can communicate if they are within communicationrange of each other, and otherwise cannot.2This paper uses a more sophisticated model of communi-cation similar to that described by Srinivas and Modiano [3].We assume that the throughput (data rate) that can be achievedbetween a regular node and a mobile backbone node is amonotonically nonincreasing function of both the distancebetween the two nodes and the number of other regularnodes that are also communicating with that particular mobilebackbone node and thus causing interference. While our resultsare valid for any throughput function that is monotonicallynonincreasing in both distance and cluster size, it is usefulto gain intuition by considering a particular example. Onesuch example is the throughput function resulting from theuse of a Slotted Aloha communication protocol in which allregular nodes are equally likely to transmit. In this protocol,the throughput τ between regular node i and mobile backbonenode j is given byτ (Aj,di j) =1Aj(1 −1Aj)(|Aj|−1)(1dαi j), (1)whereAjis the number of regular nodes assigned to mobilebackbone node j, di jis the distance between regular node iand mobile backbone node j, and α is the path loss exponent.As noted in Ref. [3], one can use the fact that(1 −1c)c−1≈1efor c > 0 to obtain a simpler expression for the SlottedAloha throughput function. In this simplified expression, thethroughput is given byτ (Aj,di j) ≈1e ·Aj· dαi j(2)where e is the base of the natural