Services such as garbage collection, road gritting, street sweeping, and power line inspection can each be formulated as a capacitated arc routing problem (CARP). The traditional formulation of CARP has the goal of minimizing the total cost of the routes making up a solution. Recently, operators of such services require routes that are balanced and visually attractive in addition to low cost. Routes that are balanced are about equal in length and provide fair work assignments. Visually attractive routes are subjective, but they usually involve non-crossing routes that provide well defined service areas. These additional features are important because they address operational complexities that arise from using the routes in practice. This paper presents MA-ABC, a memetic algorithm to find solutions for CARP that maximize route attractiveness and balance, while minimizing total cost. A novel fitness function combines route overlap with route contiguity to assess route attractiveness. MA-ABC is the first to incorporate attractiveness in a three-objective search for heuristic solutions for CARP. Experimental results on CARP benchmark instances show that MA-ABC finds a diverse set of heuristic solutions at the Pareto front, providing a wide choice for service operators to tradeoff design objectives.

We model residential waste collection as a Capacitated Arc Routing Problem (CARP). Because the collection vehicles are expensive, many public works departments cannot afford extra vehicles on hand if one breaks down. A conventional solution is for the unserved streets in the route of the broken down vehicle to be served by one of the others in the fleet as an overtime job. Instead, we propose to distribute the unserved streets among all remaining operational vehicles when a breakdown occurs. We propose PROBE, an algorithm to dynamically re-route collection vehicles in the event of a breakdown, with the objective to minimize the makespan. We evaluate PROBE on the classical CARP benchmark instances GDB, VAL, EGL, and EGL-Large. Compared to the conventional solution, PROBE obtains reduced makespan, range, and discrepancies which indicate improved balance of the solution. The run time of PROBE is linear in the number of required edges suggesting good scalability.

The Network Innovators Community Event (GENI NICE) is the premier event for researchers to demonstrate and present research results and to discuss work in progress related to the NSF's Global Environment for Network Innovations (GENI) and related advanced cyberinfrastructure testbeds.

The production network at Arizona State University uses a commercial load balancer for syslog messages from the firewalls at the data center perimeter. The logs are carried in UDP packets and the load balancer divides the load among servers based on the source IP address. This may cause a server to be overwhelmed due to the high incoming data rate, and create log files unequal in size. These logs are processed by splunk, an application for analyzing the massive streams of data generated by IT systems. In a testbed with an OpenFlow switch and three rsyslog servers, fed by a mirror of the firewall rsyslog traffic, we study controllers implementing round-robin, random, and load-based load balancing policies. All policies achieve delivery ratios comparable with the commercial load balancer. When servers fail or go down for maintenance, the load-based policy produces log files the most balanced in size. The results suggest that an OpenFlow load balancer has performance competitive with a commercial load balancer, and can equalize the log file size at servers which improves the efficiency of splunk.

The largest strength of contention-based MAC protocols is simultaneously the largest weakness of their scheduled counterparts: the ability to adapt to changes in network conditions. For scheduling to be competitive in mobile wireless networks, continuous adaptation must be addressed. We propose ATLAS, an Adaptive Topology- and Load-Aware Scheduling protocol to address this problem. In ATLAS, each node employs a random schedule achieving its persistence, the fraction of time a node is permitted to transmit, that is computed in a topology and load dependent manner. A distributed auction (REACT) piggybacks offers and claims onto existing network traffic to compute a lexicographic max-min channel allocation. A node's persistence p is related to its allocation. Its schedule achieving p is updated where and when needed, without waiting for a frame boundary. We study how ATLAS adapts to controlled changes in topology and load. Our results show that ATLAS adapts to most network changes in less than 0.1s, with about 20 percent relative error, scaling with network size. We further study ATLAS in more dynamic networks showing that it keeps up with changes in topology and load sufficient for TCP to sustain multi-hop flows, a struggle in IEEE 802.11 networks. The stable performance of ATLAS supports the design of higher-layer services that inform, and are informed by, the underlying communication network.

The primary function of the medium access control (MAC) protocol is managing access to the shared communication channel. From the viewpoint of the transmitters, the MAC protocol determines each transmitter's channel occupancy, the fraction of time that it spends transmitting over the channel. In this paper, we define a set of topological persistences that conform to both network topology and traffic load. We employ these persistences as target occupancies for the MAC layer protocol. A centralized algorithm is developed for calculating topological persistences and its correctness is established. A distributed algorithm and implementation are developed that can operate within scheduled and contention-based MAC protocols. In the distributed algorithm, network resources are allocated through auctions at each receiver in which transmitters participate as bidders to converge on the topological allocation. Very low overhead is achieved by piggybacking auction and bidder communication on existing data packets. The practicality of the distributed algorithm is demonstrated in a wireless network via simulation using the ns-2 network simulator. Simulation results show fast convergence to the topological solution and, once operating with topological persistences, improved performance compared to IEEE 802.11 in delay, throughput, and drop rate.

Cognitive radios (CRs) can dynamically reconfigure their transmission and/or reception parameters. In a cognitive radio ad hoc network (CRAHN) setting, such reconfiguration is challenging due to the lack of centralized control and fixed infrastructure. In this paper, we propose a method to improve the throughput of secondary users (SUs) in a CRAHN by dynamically adapting their sensing and transmission times. First, we conduct a designed experiment on five CR parameters in the ns-2 network simulator with extensions to support CRAHNs. A statistical analysis of the resulting data attributes the contribution of each parameter, and interactions among them, to SU throughput. Based on these results, we propose for each SU to measure its instantaneous throughput and adapt its sensing and transmission times according to the predicted throughput. Simulation results demonstrate that SUs achieve higher throughput by adapting their sensing and transmission times than by using default static values for these parameters.

In an effort to reduce overhead in proactive protocols, rather than use a global period for transmission of control information, we propose to transmit based on changes in a node's local conditions. For OLSR, a proactive link-state routing protocol, we use a significant change in the number of edges in a node's two-hop neighbourhood and topological graph as indicators of topology change warranting an update. When the associated exponentially weighted moving average (EWMA) charts and multivariate EWMA chart signal out-of-control, a node transmits a HELLO, a topology control (TC), or both HELLO and TC messages. We use ns-2 simulations to compare OLSR to our TS-OLSR, and other variants of OLSR. We find that TS-OLSR obtains a statistically significant reduction in overhead compared to the other protocols while maintaining the packet delivery ratio. The approach is general and may find use in other applications requiring response to changes in local conditions.

We present a multi-channel MAC protocol for ad hoc networks, for nodes equipped with a single half-duplex transceiver, combining the use of OFDMA and CDMA. To ease OFDMA channel management the network is clustered. Channel groups are defined by a resolvable balanced incomplete block design (BIBD) to minimize interference. Unique CDMA codes are assigned to each cluster. Clusterheads manage and assign channel groups through an extended handshake. Idle nodes that overhear the handshake cooperate to reduce the incidence of the multi-channel hidden- and exposed-terminal problems, and also the near-far problem of CDMA. Simulation results show a significant improvement in average delivery ratio and delay, especially in dense network topologies.

Comparison of schedule and contention based MAC protocols is made difficult by their fundamental differences in approach to medium access control. This paper provides a way in which to analyze and compare MAC protocols regardless of their underlying allocation strategy. To that end a framework is developed in which the persistence of any protocol, contention- or schedule-based, can be measured. The framework is used to measure and compare the persistence levels of two prototypical contention- and schedule-based MACs, IEEE 802.11 and Scheduled p-Persistence. An ideal persistence that provides lexicographically max-min fair access to the channel is characterized, and used as a bandwidth allocation scheme. In addition to reducing the unfairness, simulations employing the ideal persistence values show increased throughput and decreased delay and drop rate when compared to either Scheduled p-Persistence or IEEE 802.11.

Abstract In a problem arising in grooming for two‐period optical networks, it is required to decompose the complete graph on n vertices into subgraphs each containing at most C edges, so that the induced subgraphs on a specified set of v ≤ n vertices each contain at most C ′ < C edges. The cost of the grooming is the sum, over all subgraphs, of the number of vertices of nonzero degree in the subgraph. The optimum grooming is the one of lowest cost. An integer linear programming formulation is used to determine precise lower bounds on this minimum cost for all choices of n and v when 1 ≤ C ′ < C ≤ 3. In most cases, this approach determines not only the bound but also the specific structure of any grooming that could realize the bound. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract Minimizing the number of add‐drop multiplexers (ADMs) in a unidirectional SONET ring can be formulated as a graph decomposition problem. When traffic requirements are uniform and all‐to‐all, groomings that minimize the number of ADMs (equivalently, the drop cost) have been characterized for grooming ratio at most six. However, when two different traffic requirements are supported, these solutions do not ensure optimality. In two‐period optical networks, n vertices are required to support a grooming ratio of C a in the first time period, while in the second time period a grooming ratio of C b , C b < C a , is required for v ≤ n vertices. This allows the two‐period grooming problem to be expressed as an optimization problem on graph decompositions of K n that embed graph decompositions of K v for v ≤ n . Using this formulation, optimal two‐period groomings are found for small grooming ratios using techniques from the theory of graphs and designs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Despite its success in saving energy and increasing spatial reuse, the use of variable transmission power control in wireless multihop networks has consequences to fairness. We study a variant of the hidden terminal problem resulting from link asymmetries, and its impact on expected node throughput. We give a model relating the transmission power level and backoff window size to throughput. Based on the analysis, we propose a localized algorithm to set the contention window size of a medium access control protocol according to the transmission power level. In simulation our protocol achieves the highest fairness index among several approaches.

Our goal is to save energy in wireless sensor networks (WSNs) by periodic duty-cycling of sensor nodes. We schedule sensor nodes between active (transmit or receive) and sleep modes while bounding packet latency in the presence of collisions. In order to support a dynamic WSN topology, we focus on topology-transparent approaches to scheduling; these are independent of detailed topology information. Much work has been done on topology-transparent scheduling in which all nodes are active. In this work, we examine the connection between topology-transparent duty-cycling and such non-sleeping schedules. This suggests a way to construct topology-transparent duty-cycling schedules. We analyse the performance of topology-transparent schedules with a focus on throughput in the worst case. A construction of topology-transparent duty-cycling schedules based on a topology-transparent non-sleeping schedule is proposed. The constructed schedule achieves the maximum average throughput in the worst case if the given non-sleeping schedule satisfies certain properties.

Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop (vi, vj), communication is effective only when viis transmitting, vjis receiving, and no other node in proximity of vjis also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use arc-decompositions of the complete lambda-fold directed graph Koarrninto directed complete bipartite subgraphs Koarra,bas a model for ternary scheduling in WSNs. We associate the vertices of Koarrnwith the nodes of the WSN, and occurrences of Koarra,bs (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of lambdaKoarrnguarantees that every ordered pair of nodes in the WSN can communicate in lambda time slots.

We present an application of the Redback network dynamics analysis tool to mobile ad hoc networks. Our goal is to understand the network properties that arise from different mobility models and to quantify how these differences impact communications. We generate input for Redback as a graph series for varying node density and speed in the random waypoint, reference point group, freeway, and Manhattan mobility models by sampling network topology in the ns-2 network simulator. The graph series are analyzed using several distance and metric measures in the Redback tool and visualized as a time series, one of the Redback output displays. We find measurable differences among mobility models that may impact mobile communications and influence protocol design.

Abstract-Response surface methodology (RSM) is a collection of statistical design and numerical optimization techniques traditionally used to optimize industrial processes. In this paper, we demonstrate that the methodology can be successfully applied to the domain of networking. Specifically, we obtain increased throughput with a significant decrease in delay in a ns-2 simulation model of a mobile ad hoc network (MANET) by using RSM to optimize protocol interaction found by factor screening. Whether the experimentation is with a stochastic simulation model or a physical system, such as a MANET or a wireless sensor network test-bed, RSM provides a general and practical methodology to screen factors and robustly and jointly optimize responses.

Summary form only given. Topology transparent scheduling for medium access control is an attractive technique for mobile ad hoc networks (MANETs) and sensor networks. The transmission schedule for each node is fixed and guarantees a bounded delay independent of which nodes are its neighbours, as long as the network is not too dense. Constructions of and performance criteria for topology transparent schedules have been extensively studied however, to date, frame synchronization is assumed. Synchronization is a difficult problem for MANETs and sensor networks. We study the relationships among topology transparent schedules, synchronization, and maximum delay. Frame synchronization, slot synchronization, and asynchronous transmission are the three synchronization models for this study. For each synchronization model, the first question is: (1) Do topology transparent schedules exist? If the answer to this question is yes, then two further questions are natural: (2) How to construct topology transparent schedules? (3) What is the least maximum delay? For frame and slot synchronization these three questions are answered in earlier work. We give answers for these three basic questions for asynchronous networks.

For sensor networks, throughput may not be the most important metric to optimize in medium access control. For many applications, periodic reports are desirable suggesting the need for a time division (TDMA) access scheme. However for many reasons, including nonuniformity of deployment and the large number of sensor nodes anticipated, TDMA is impractical. We explore scheduled persistence for medium access control in sensor networks. A continuum of approaches from simple randomized-persistent schedules at one extreme to topology-transparent schedules based on Steiner systems at the other are considered. We investigate the probability of obtaining a collision-free slot before a specified time (number of slots) and show that while the expected throughput of these approaches is the same, their variance is strikingly different. The schemes are also remarkably robust to high density. Furthermore, when schedules are chosen at random for each frame, scheduled persistence offers an interesting alternative for medium access control in sensor networks.

We deal with the problem of topology control for mobile ad hoc networks. Based on an asymptotic result on k-connectivity, a simple scheme for topology control is proposed. The scheme is used to generate several topologies under highly mobile conditions. Through simulation and analysis we show that this scheme results in high connectivity even under mobile conditions as the number of nodes increase. We also show that even though the scheme uses varying transmit power, the overall power consumption in the network remains relatively the same, and is less than using constant transmit power as the number of nodes increases. In order to use the scheme, the nodes need to he uniformly distributed. We prove that under periodic boundary conditions the stationary distribution of nodes, moving according to (a variant of) the random waypoint model, is uniform.

Delay sensitive applications are driving the need for the support of quality-of-service (QoS) in mobile ad hoc networks. In this paper, we use statistical design of experiments to study the impact of factors and their interaction on the service delivered. We consider the factors of QoS architecture, routing protocol, medium access control protocol, offered load, and mobility, at mixed levels. Real-time throughput, total throughput, and average delay are used as the measures of service delivery. A statistical analysis of the data collected by simulation using analysis of variance techniques is performed. This allows us to identify both main effects and interactions of factors that best explain the response variables. For average delay several factors of the experiment interact. For both forms of throughput, the impact of the routing protocol is not apparent except as it interacts with other factors, and the factor interactions are not as extensive as for delay. Thus, for all response variables the factors cannot be studied in isolation. As well, the analysis provides a means for a system architect to determine the level to set the factors to optimize a specific service delivery metric, or combination of metrics.

MERIT is a framework to assess routing protocols in mobile Ad hoc networks (manets). It is based on the novel concept of a shortest mobile path (SMP) in a mobile qraph, generalizing the traditional shortest path concept for the mobile environment. As a standard measure for routing protocols in a manet, the MERIT framework proposes the mean ratio of the cost of the actually used route to the cost of the optimal mobile path, under the same history of link metrics in the changing network topology. The MERIT spectrum takes the MERIT ratio as a function of parameters of interest yielding a multi-faceted representation of protocol effectiveness. This Mean Real vs. Ideal cosT (MERIT) framework is unifying in that it provides a measure that allows a protocol to be assessed independently of other protocols, within its own environment. We show that there is an efficient algorithm to solve the underlying SMP problem for important cases, making the approach practically feasible. We also investigate generalizations of and extensions within the MERIT framework.

A systematic and automatic method for dynamically optimizing medium access control (MAC) protocol parameters is presented. Our meta-protocol approach is capable of performing on-line optimization of critical MAC parameters without knowing in advance what network conditions will arise or how they may fluctuate over time. Furthermore, this dynamic optimization is achieved without any centralized control or exchange of control messages between nodes. The power of the new technique is demonstrated by two examples. In a LAN environment, it outperforms traditional contention based MAC protocols that adjust retransmission probabilities, e.g., employing binary exponential backoff. In a synchronous multi-hop environment, it automatically converges to the proper transmission schedule assignments for the actual node density.

This paper presents ABROAD, an adaptive medium access control (MAC) protocol for reliable broadcast packet transmission in wireless networks. ABROAD incorporates a collision-avoidance handshake within each slot of a synchronous transmission schedule, allowing nodes to reclaim and/or reuse idle slots while maintaining bounded access delay. Thus, ABROAD provides worst-case performance guarantees while remaining adaptive to local changes in traffic load and node connectivity. We analyze the optimal worst-case performance of ABROAD, and show that there is a strict increase in the number of broadcast packets per second over a pure time division multiple access (TDMA) protocol. Extensive simulation confirms our analysis, and also demonstrates that ABROAD outperforms broadcast protocols based on reliable unicast packet delivery schemes, such as the IEEE 802.11 MAC standard.

This paper introduces OLAM, a novel on-demand location aware multicast protocol for ad hoc networks. The protocol assumes that, through the use of positioning system devices, such as Global Positioning System (GPS) devices, each node knows its own position and the current (global) time, and it is able to efficiently distribute these measures, including its current transmission radius, to all other nodes. As the measures are received, each node updates its local snapshot of the complete network topology. When a packet is to be multicast to a group, a heuristic is then used to locally compute the Steiner (i.e., multicast) tree for the addressed multicast group based on the snapshot rather than maintaining the tree in a distributed manner. The resulting Steiner tree is then optimally encoded by using its unique Prufer sequence and included along with the packet, extending the length of the header by no more than the header of packets in source routing (unicast) techniques. All local computations are executed using efficient (i.e., polynomial time) algorithms. The protocol has been simulated in ad hoc networks with 30 and 60 nodes and with different multicast group sizes. We show that OLAM delivers packets to all the nodes in a destination group in more than 85% of the cases. Furthermore, compared to flooding, OLAM achieves improvements of up to 50% on multicast completion delay.

A systematic and automatic method to dynamically combine any set of existing MAC protocols into a single higher layer, or meta-MAC protocol, is presented. The new approach makes it possible to always achieve the performance of the best component protocol, without knowing in advance which protocol will match the potentially changing and unpredictable network conditions. Moreover, this dynamic optimization is entirely automatic and runs without any centralized control or any exchange of messages, using only local network feedback information. We describe the method and prove that the resulting meta-MAC protocol achieves optimal performance in a well-defined sense. Through simulation on different types of networks and with different component MAC protocols, we demonstrate that our simple and practical combination algorithm yields highly adaptive and scalable MAC solutions.

This paper proposes a new routing protocol for ad hoc networks built around the source routing technique combined with the location (e.g., GPS coordinates) of nodes obtained by an energy and distance smart dissemination mechanism. The key new observation used is that the location information provides each node with a snapshot of the topology of the complete network from which a source route may be computed locally rather than through route discovery. The resulting protocol has reduced delay, and is more bandwidth and energy efficient, than both traditional (proactive and reactive) ad hoc routing protocols, as well as location based routing protocols.

Article Free Access Share on A distance routing effect algorithm for mobility (DREAM) Authors: Stefano Basagni Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile , Imrich Chlamtac Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile , Violet R. Syrotiuk Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile , Barry A. Woodward Erik Jonsson School of Engineering and Computer Science, The University of Texas at Dallas Erik Jonsson School of Engineering and Computer Science, The University of Texas at DallasView Profile Authors Info & Claims MobiCom '98: Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networkingOctober 1998 Pages 76–84https://doi.org/10.1145/288235.288254Published:25 October 1998Publication History 704citation5,003DownloadsMetricsTotal Citations704Total Downloads5,003Last 12 Months353Last 6 weeks41 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF