Optimal and approximate approaches for selecting proxy agents in mobile IP based network backbones

In a mobile environment, each mobile host should have a home agent on its home network that maintains a registry of the current location of the mobile host. This registry is normally updated every time a mobile host moves from one subnet to another. We study the tradeoff between the cost of updating the registry and the cost of searching for a mobile host while it is away from home. Using a set of special agents, called proxy agents, which implement a two-tier update process, the cost of updates could be reduced; however, the search cost might increase. We study different approaches to identify a set of proxy agents that minimizes the cost of search. In this paper, we use mathematical programming to obtain optimal solutions to the problem. We consider two situations: the cost of search measured by the sum of all search message costs, and the cost of search measured by the maximum cost of such messages. For these two respective cases we formulate the minimization of the cost of search as Min-Sum and Min-Max problems. For large networks in which the optimization problem may be intractable, we study three different approximate approaches: (1) clustering, (2) genetic algorithms, and (3) simulated annealing. Results of a large set of experiments are presented.     

树形网络中的副本更新策略及算法

树形网络中的副本放置和更新是网络通讯中值得研究的重要问题之一。面对网络中数据访问需求的动态变化,好的副本放置和更新策略可以在保证服务质量的前提下有效减少网络运行及副本更新成本。针对此问题提出了两种贪心的动态副本更新策略,最大重用策略和请求覆盖策略。通过算法复杂度分析和仿真实验可以看出,所提出的两种算法的最坏时间复杂度为O(nlog n),远低于现有的使用动态规划求最优解的最坏时间复杂度O(n5),而网络运行及副本更新成本与最优解相差不超过11%。在极大地缩短了运算时间的同时,保持了尽可能低的网络运行及副本更新成本。     

An update-based step-wise optimal cache replacement for wireless data access

Many network applications requires access to most up-to-date information. An update event makes the corresponding cached data item obsolete, and cache hits due to obsolete data items become simply useless to those applications. Frequently accessed but infrequently updated data items should get higher preference while caching, and infrequently accessed but frequently updated items should have lower preference. Such items may not be cached at all or should be evicted from the cache to accommodate items with higher preference. In wireless networks, remote data access is typically more expensive than in wired networks. Hence, an efficient caching scheme considers both data access and update patterns can better reduce data transmissions in wireless networks. In this paper, we propose a step-wise optimal update-based replacement policy, called the Update-based Step-wise Optimal (USO) policy, for wireless data networks to optimize transmission cost by increasing effective hit ratio. Our cache replacement policy is based on the idea of giving preference to frequently accessed but infrequently updated data, and is supported by an analytical model with quantitative analysis. We also present results from our extensive simulations. We demonstrate that (1) the analytical model is validated by the simulation results and (2) the proposed scheme outperforms the Least Frequently Used (LFU) scheme in terms of effective hit ratio and communication cost.     

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.     

Dynamic distributed unicast routing: optimal incremental paths

Developing new mathematical frameworks such as distributed dynamic routing algorithms for constructing optimal incremental paths from a node to another node is an important challenge in data communication networks. These new algorithms can model network resources optimally and increase network performances. A bundle of single routes in a current communication path, which starts from a source node and ends to a destination node, can consist of several successive nodes and links. The Incremental term emphasizes that the number of routes (links and nodes) in a current path can change so that achieving more data rate and optimal efficiency in the network. In this paper, our problem is to add/omit some routes consisting of some nodes and links to/from the current unicast path dynamically and optimally. We call this problem the Optimal Dynamic Distributed Unicast Routing (ODDUR) problem and it is a NP-complete problem. This problem can be formulated as a new type of Linear Programming Problem (LPP) for finding a minimum cost multichannel unicast path, which this path will minimize end-to-end delay and bandwidth consumption along the routes from the source node to the destination node. In this paper, at first a new mathematical framework will be constructed and then this framework will propose the new optimal dynamic distributed unicast routing algorithm for solving our LPP problem. This algorithm will compute an optimal solution for our LPP based on the simplex method and postoptimality computations and will reduce computations and consumed time. Simulation results will show that our new algorithm is more efficient than other available algorithms in terms of utilization of bandwidths and data rate.     

Stochastic shortest path with unlimited hops

We present new results for the Stochastic Shortest Path problem when an unlimited number of hops may be used. Nodes and links in the network may be congested or uncongested, and their states change over time. The goal is to adaptively choose the next node to visit such that the expected cost to the destination is minimized. Since the state of a node may change, having the option to revisit a node can improve the expected cost. Therefore, the option to use an unbounded number of hops may be required to achieve the minimum expected cost. We show that when revisits are prohibited, the optimal routing problem is np-hard. We also prove properties about networks for which continual improvement may occur.We study the related routing problem which asks whether it is possible to determine the optimal next node based on the current node and state, when an unlimited number of hops is allowed. We show that as the number of hops increases, this problem may not converge to a solution.     

Optimal distribution of a hierarchy of network management agents

In this paper, we consider several mathematical and algorithmic problems which arise naturally in the optimal deployment of modern network management systems. Specifically, we will consider the problem of minimizing the total communication costs within an architecture consisting of a distributed hierarchy of cooperating intelligent agents. We consider several communication cost models, and describe provable optimal schemes for distributing agents among machines in each of these models.     

基于误码率与中断概率约束的femtocell网络分布式功率控制

家庭基站(femtocell)网络可有效改善无线通信业务的室内覆盖性能,提高信道容量.然而,复杂的动态通信环境导致信道的不确定性,影响用户服务质量.基于此,研究双层femtocell网络在快衰落信道环境下基于误码率约束的功率控制问题;考虑信号传输的中断概率,以及服务质量指标–误码率等方面的要求,构造在此约束下的优化问题;最大化双层femtocell网络的净收益,使得网络系统的通信性能最优;通过对概率约束进行数学处理,将其转化为确定性形式,并提出分布式鲁棒优化算法对等价的确定性优化问题进行求解,从而获得最优功率分配策略.最后,通过仿真验证了所提出算法的收敛性和有效性.     

QoS-aware,access-efficient,and storage-efficient replica placement in grid environments

In this paper, we study the quality-of-service (QoS)-aware replica placement problem in grid environments. Although there has been much work on the replica placement problem in parallel and distributed systems, most of them concern average system performance and have not addressed the important issue of quality of service requirement. In the very few existing work that takes QoS into consideration, a simplified replication model is assumed; therefore, their solution may not be applicable to real systems. In this paper, we propose a more realistic model for replica placement, which consider storage cost, update cost, and access cost of data replication, and also assumes that the capacity of each replica server is bounded. The QoS-aware replica placement is NP-complete even in the simple model. We propose two heuristic algorithms, called greedy remove and greedy add to approximate the optimal solution. Our extensive experiment results demonstrate that both greedy remove and greedy add find a near-optimal solution effectively and efficiently. Our algorithms can also adapt to various parallel and distributed environments.     

Semidynamic Algorithms for Maintaining Single-Source Shortest Path Trees

We consider the problem of updating a single-source shortest path in either a directed or an undirected graph, with positive real edge weights. Our algorithms for the incremental problem (handling edge insertions and cost decrements) work for any graph; they have optimal space requirements and query time, but their performances depend on the class of the considered graph. The cost of updates is computed in terms of amortized complexity and depends on the size of the output modifications. In the case of graphs with bounded genus (including planar graphs), graphs with bounded arboricity (including bounded degree graphs), and graphs with bounded treewidth, the incremental algorithms require O(log n) amortized time per vertex update, where a vertex is considered updated if it reduces its distance from the source. For general graphs with n vertices and m edges our incremental solution requires O( log n) amortized time per vertex update. We also consider the decremental problem for planar graphs, providing algorithms and data structures with analogous performances. The algorithms, based on Dijkstra's technique [6], require simple data structures that are really suitable for a practical and straightforward implementation. Received January 1995; revised February 1997.     

Constrained optimal consensus in multi-agent systems with single- and double-integrator dynamics

ABSTRACT

This paper fully studies distributed optimal consensus problem in undirected dynamical networks. We consider a group of networked agents that are supposed to rendezvous at the optimal point of a collective convex objective function. Each agent has no knowledge about the global objective function and only has access to its own local objective function, which is a portion of the global one, and states information of agents within its neighbourhood set. In this setup, all agents coordinate with their neighbours to seek the consensus point that minimises the network's global objective function. In the current paper, we consider agents with single-integrator and double-integrator dynamics. Further, it is supposed that agents' movements are limited by some convex inequality constraints. In order to find the optimal consensus point under the described scenario, we combine the interior-point optimisation algorithm with a consensus protocol and propose a distributed control law. The associated convergence analysis based on Lyapunov stability analysis is provided.     

Group registration with distributed databases for location tracking in 3G wireless networks

The increase of subscribers in wireless networks has led to the need for efficient location tracking strategies. Location tracking is used to keep track of a Mobile Terminal (MT). The network retains the Registration Area (RA), where the MT last updated its location, so when an incoming call arrives for the MT, the network with the help of a location tracking strategy can find the area where the MT resides and then deliver the call. In this paper, we introduce a 2-level distributed database architecture combined with the Group Registration (GR) location tracking strategy to be used in 3G wireless networks. The GR strategy reduces the location management total cost, by updating the location of MTs in an RA with a single route response message to the HSS (Home Subscriber Server). More specifically, the IDs of the MTs newly moving into an RA are buffered and sent to the HSS for location updating in the route response message of the next incoming call to any MT in the RA. An analytical model is developed and numerical results are presented. It is shown that the GR strategy integrated with a 2-level distributed databases architecture in 3G networks can achieve location management cost reduction compared to costs of the distributed databases without the GR strategy and the GR strategy without distributed databases. Moreover, the proposed strategy results in small call delivery latency.     

Detecting proximity events in sensor networks

Sensor networks are often used to perform monitoring tasks, such as animal and vehicle tracking, or the surveillance of enemy forces in military applications. In this paper we introduce the concept of proximity queries, which allow us to report interesting events, observed by nodes in the network that lie within a certain distance from each other. An event is triggered when a user-programmable predicate is satisfied on a sensor node. We study the problem of computing proximity queries in sensor networks and propose several alternative techniques that differ in the number of messages exchanged by the nodes and the quality of the returned answers. Our solutions utilize a distributed routing index, maintained by the nodes in the network, that is dynamically updated as new observations are obtained by the nodes. This distributed index allows us to efficiently process multiple proximity queries involving several different event types within a fraction of the cost that a straightforward evaluation requires. We present an extensive experimental study to show the benefits of our techniques under different scenarios using both synthetic and real data sets. Our results demonstrate that our algorithms scale better and require significantly fewer messages compared to a straightforward execution of the queries.     

Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality

Motivated by recent applications of wireless sensor networks in monitoring infrastructure networks, we address the problem of optimal coverage of infrastructure networks using sensors whose sensing performance decays with distance. We show that this problem can be formulated as a continuous p-median problem on networks. The literature has addressed the discrete p-median problem   on networks and in continuum domains, and the continuous p$p$-median problem in continuum domains extensively. However, in-depth analysis of the continuous p$p$-median problem on networks has been lacking. With the sensing performance model that decays with distance, each sensor covers a region equivalent to its Voronoi partition on the network in terms of the shortest path distance metric. Using Voronoi partitions, we define a directional partial derivative of the coverage metric with respect to a sensor’s location. We then propose a gradient descent algorithm to obtain a locally optimal solution with guaranteed convergence. The quality of an optimal solution depends on the choice of the initial configuration of sensors. We obtain an initial configuration using two approaches: by solving the discrete p$p$-median problem on a lumped   network and by random sampling. We consider two methods of random sampling: uniform sampling and D²$D^2$-sampling. The first approach with the initial solution of the discrete p$p$-median problem leads to the best coverage performance for large networks, but at the cost of high running time. We also observe that the gradient descent on the initial solution with the D²$D^2$-sampling method yields a solution that is within at most 7% of the previous solution and with much shorter running time.     

Combinatorial optimization in Biology using Probability Collectives Multi-agent Systems

We present a study of Probability Collectives Multi-agent Systems (PCMAS) for combinational optimization problems in Biology. This framework for distributed optimization is deeply connected with both game theory and statistical physics. In contrast to traditional biologically-inspired algorithms, Probability-Collectives (PC) based methods do not update populations of solutions; instead, they update an explicitly parameterized probability distribution p over the space of solutions by a collective of agents. That updating of p arises as the optimization of a functional of p. The functional is chosen so that any p that optimizes it should be p peaked about good solutions. In this paper we demonstrate PCMAS as a promising combinational optimization method for biological network construction. This computational approach to response networks enables robust prediction of activated crucial sub-networks in biological systems under the presence of specific drugs, thereby facilitating the identification of important nodes for potential drug targets and furthering hypotheses about biological and medical problems on a systems level. The application of PCMAS in this context therefore sheds light on how this multi-agent learning methodology advances the current state of research in agent-based models for combinational optimization problems in Biology.     

A distributed simplex algorithm for degenerate linear programs and multi-agent assignments

In this paper we propose a novel distributed algorithm to solve degenerate linear programs on asynchronous peer-to-peer networks with distributed information structures. We propose a distributed version of the well-known simplex algorithm for general degenerate linear programs. A network of agents, running our algorithm, will agree on a common optimal solution, even if the optimal solution is not unique, or will determine infeasibility or unboundedness of the problem. We establish how the multi-agent assignment problem can be efficiently solved by means of our distributed simplex algorithm. We provide simulations supporting the conjecture that the completion time scales linearly with the diameter of the communication graph.     

Cut-and-solve: An iterative search strategy for combinatorial optimization problems

Branch-and-bound and branch-and-cut use search trees to identify optimal solutions to combinatorial optimization problems. In this paper, we introduce an iterative search strategy which we refer to as cut-and-solve and prove optimality and termination for this method. This search is different from traditional tree search as there is no branching. At each node in the search path, a relaxed problem and a sparse problem are solved and a constraint is added to the relaxed problem. The sparse problems provide incumbent solutions. When the constraining of the relaxed problem becomes tight enough, its solution value becomes no better than the incumbent solution value. At this point, the incumbent solution is declared to be optimal. This strategy is easily adapted to be an anytime algorithm as an incumbent solution is found at the root node and continuously updated during the search.Cut-and-solve enjoys two favorable properties. Since there is no branching, there are no “wrong” subtrees in which the search may get lost. Furthermore, its memory requirement is negligible. For these reasons, it has potential for problems that are difficult to solve using depth-first or best-first search tree methods.In this paper, we demonstrate the cut-and-solve strategy by implementing a generic version of it for the Asymmetric Traveling Salesman Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art solvers for five out of seven real-world problem classes of the ATSP. For four of these classes, cut-and-solve was able to solve larger (sometimes substantially larger) problems. Our code is available at our websites.     

Optimal Content Location in Multicast Based Overlay Networks with Content Updates

The architecture of overlay networks should support high-performance and high-scalability at low costs. This becomes more crucial when communication, storage costs as well as service latencies grow with the exploding amounts of data exchanged and with the size and span of the overlay network. For that end, multicast methodologies can be used to deliver content from regional servers to end users, as well as for the timely and economical synchronization of content among the distributed servers. Another important architectural problem is the efficient allocation of objects to servers to minimize storage, delivery and update costs. In this work, we suggest a multicast based architecture and address the optimal allocation and replication of dynamic objects that are both consumed and updated. Our model network includes consumers which are served using multicast or unicast transmissions and media sources (that may be also consumers) which update the objects using multicast communication. General costs are associated with distribution (download) and update traffic as well as the storage of objects in the servers. Optimal object allocation algorithms for tree networks are presented with complexities of O(N) and O(N ²) in case of multicast and unicast distribution respectively. To our knowledge, the model of multicast distribution combined with multicast updates has not been analytically dealt before, despite its popularity in the industry.     

The cost optimal solution of the multi-constrained multicast routing problem

In this paper, we define the cost optimal solution of the multi-constrained multicast routing problem. This problem consists in finding a multicast structure that spans a source node and a set of destinations with respect to a set of constraints, while minimizing a cost function. This optimization is particularly interesting for multicast network communications that require Quality of Service (QoS) guarantees. Finding such a structure that satisfies the set of constraints is an NP-hard problem. To solve the addressed routing problem, most of the proposed algorithms focus on multicast trees. In some cases, the optimal spanning structure (i.e. the optimal multicast route) is neither a tree nor a set of trees nor a set of optimal QoS paths. The main result of our study is the exact identification of this optimal solution. We demonstrate that the optimal connected partial spanning structure that solves the multi-constrained multicast routing problem always corresponds to a hierarchy, a recently proposed generalization of the tree concept. We define the directed partial minimum spanning hierarchies as optimal solutions for the multi-constrained multicast routing problem and analyze their relevant properties. To our knowledge, our paper is the first study that exactly describes the cost optimal solution of this NP-hard problem.     

Learning Communication Strategies in Multiagent Systems

In this paper we describe a dynamic, adaptive communication strategy for multiagent systems. We discuss the behavioral parameters of each agent that need to be computed, and provide a quantitative solution to the problem of controlling these parameters. We also describe the testbed we built and the experiments we performed to evaluate the effectiveness of our methodology. Several experiments using varying populations and varying organizations of agents were performed and are reported. A number of performance measurements were collected as each experiment was performed so the effectiveness of the adaptive communications strategy could be measured quantitatively.The adaptive communications strategy proved effective for fully connected networks of agents. The performance of these experiments improved for larger populations of agents and even approached optimal performance levels. Experiments with non-fully connected networks showed that the adaptive communications strategy is extremely effective, but does not approach optimality. Other experiments investigated the ability of the adaptive communications strategy to compensate for distracting agents, for systems where agents are required to assume the role of information routers, and for systems that must decide between routing paths based on cost information.