Throughput Optimization inMobile Backbone Networks

Abstract—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 backbone

Networks 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.

Approximation Algorithm

Approximation algorithm withapproximation guarantee 1 ?1e. Additionally, because eachround of greedy selection consists of solving a polynomialnumber of maximum flow problems on graphs with at mostN +2L+K +2 nodes, and there are K rounds of selection,the running time of Algorithm 2 is polynomial in the numberof regular nodes, the number of locations, and the numberof mobile backbone nodes. Furthermore, all network flowproblems solved by Algorithm 2 are formulated on bipartitegraphs, for which highly efficient algorithms exist

Existing System

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 Existing techniques, while exact,

Suffer from intractable computation times, even for problemsof modest size. Furthermore, mobility of regular nodes hasnot been adequately addressed.

Proposed System

This paper focuses on a hierarchical networkarchitecture called a mobile backbone network, in which mobileagents 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 backbonenetworks can be used to model a variety of multi-agentsystems.

Mobile backbone networks were described by Rubin et al.and Xu et al. as a solution to the scalability issuesinherent in mobile ad hoc networks. Noting that most communicationbandwidth in single-layer large-scale mobile networksis dedicated to packet-forwarding and routing overhead, theyproposed multi-layer hierarchical network architecture, as iscurrently used in the Internet. 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.

Fig. 1. A typical example of an optimal mobile backbonenetwork. Mobile backbone nodes, indicated by _, areplaced such that they provide communication support forregular nodes, shown as _. Each regular node is assignedto one mobile backbone node. Dashed lines indicate theradius of each cluster of nodes.

Modules

  1. Mobile backbone network optimization module

This paper focuses on a hierarchical networkarchitecture called a mobile backbone network, in which mobileagents 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 backbonenetworks can be used to model a variety of multi-agentsystems.a mobile backbone node is a

Monotonically 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.

  1. MILP approach

A primary contribution of this work is the development ofa single optimization problem that simultaneously solves themobile backbone node placement and regular node assignmentproblems. This is accomplished through the formulation of anetwork design problem.the exact(MILP) algorithm , the approximation algorithm exhibits excellentempirical performance, achieving results comparable to thoseof the exact algorithm with a great reduction in computationtime.

  1. JointPlacement of Regular and Mobile Backbone Nodes

The network design problem

Network design problem exactly describes the mobilebackbone network optimization problem with mobile regularnodes. The arcs connecting node sets N and L reflect themobility constraints of the regular nodes, while the geometricaspects of the mobile backbone node placement problem aredescribed by the arcs connecting node sets

  1. Network design formulation

A small example of mobile backbone network optimization with limited regular node movement. Open circlesrepresent possible regular node locations, and filled circles are the initial locations of the regular nodes. Shaded circlesin the left figure indicate the possible radius of motion of each regular node. In the right figure, mobile backbone nodesare placed such that they provide communication support for the regular nodes. Each regular node is assigned to atmost one mobile backbone node. Dotted lines indicate regular node motion in this optimal solution. Dashed circlesindicate the communication radius of each cluster of nodes. In this example, all regular nodes have been successfullyassigned to mobile backbone nodes

System Requirements:

Hardware Requirements:

PROCESSOR : PENTIUM IV 2.6 GHz

RAM :512 MB DD RAM

MONITOR :15” COLOR

HARD DISK :20 GB

FLOPPY DRIVE :1.44 MB

CDDRIVE :LG 52X

KEYBOARD :STANDARD 102 KEYS

MOUSE :3 BUTTONS

Software Requirements:

Front End : Java, JFC (Swing)

Tools Used : Eclipse 3.3

Operating System: Windows XP/7