Rate Allocation and Network Lifetime Problems for Wireless Sensor Networks

An important performance consideration for wireless sensor networks is the amount of information collected by all the nodes in the network over the course of network lifetime. Since the objective of maximizing the sum of rates of all the nodes in the network can lead to a severe bias in rate allocation among the nodes, we advocate the use of lexicographical max-min (LMM) rate allocation. To calculate the LMM rate allocation vector, we develop a polynomial-time algorithm by exploiting the parametric analysis (PA) technique from linear program (LP), which we call serial LP with parametric analysis (SLP-PA). We show that the SLP-PA can be also employed to address the LMM node lifetime problem much more efficiently than a state-of-the-art algorithm proposed in the literature. More important, we show that there exists an elegant duality relationship between the LMM rate allocation problem and the LMM node lifetime problem. Therefore, it is sufficient to solve only one of the two problems. Important insights can be obtained by inferring duality results for the other problem.     

Global Optimization of Nonconvex Polynomial Programming Problems Having Rational Exponents

This paper considers the solution of nonconvex polynomial programming problems that arise in various engineering design, network distribution, and location-allocation contexts. These problems generally have nonconvex polynomial objective functions and constraints, involving terms of mixed-sign coefficients (as in signomial geometric programs) that have rational exponents on variables. For such problems, we develop an extension of the Reformulation-Linearization Technique (RLT) to generate linear programming relaxations that are embedded within a branch-and-bound algorithm. Suitable branching or partitioning strategies are designed for which convergence to a global optimal solution is established. The procedure is illustrated using a numerical example, and several possible extensions and algorithmic enhancements are discussed.     

A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems

This paper presents a primal-dual conjugate subgradient algorithm for solving convex programming problems. The motivation, however, is to employ it for solving specially structured or decomposable linear programming problems. The algorithm coordinates a primal penalty function and a Lagrangian dual function, in order to generate a (geometrically) convergent sequence of primal and dual iterates. Several refinements are discussed to improve the performance of the algorithm. These are tested on some network problems, with side constraints and variables, faced by the Freight Equipment Management Program of the Association of American Railroads, and suggestions are made for implementation.This research was supported by the Association of American Railroads.     

The design of branch and bound algorithms for a class of nonlinear integer programs

This paper is concerned with computational experimentation leading to the design of effective branch and bound algorithms for an important class of nonlinear integer programming problems, namely linearly constrained problems, which are used to model several real-world situations. The main contribution here is a study of the effect of node and branching variable selection and storage reduction strategies on overall computational effort for this class of problems, as well as the generation of a set of adequate test problems. Several node and branching variable strategies are compared in the context of a pure breadth-first enumeration, as well as in a special breadth and depth enumeration combination approach presented herein. Also, the effect of using updated pseudocosts is briefly addressed. Computational experience is presented on a set of eighteen suitably-sized nonlinear test problems, as well as on some random linear integer programs. Some of the new rules proposed are demonstrated to be significantly superior to previously suggested strategies; interestingly, even for linear integer programming problems.     

A restriction and feasible direction algorithm for a capacity expansion problem

This paper examines the problem of optimally expanding existing capacity in order to meet an expected load in the context of an electric utility. A pre-optimization (Phase I) analysis is presented in order to easily determine (a) the capacities of existing equipments which will be used at an optimal solution; (b) the optimal (nonnegative) capacities of a subset of the new equipments to be purchased, and (c) a good quality starting solution. Having thus restricted a part of the solution to its optimal value, the problem is transformed into one of minimizing a convex, differentiable function, subject to a single generalized upper bounding constraint along with nonnegativity restrictions. An efficient specialization of a feasible directions algorithm (Phase II) is presented to solve this problem. The algorithm is versatile in that it provides a preview of whether or not all existing equipment capacity will be used in the light of available equipments, and which new equipments may be used in the optimal expansion plan. The algorithm can also solve the problem which enforces the use of all existing equipment capacity. Furhtermore, Phase I, which is the principal part of this algorithm, provides the user with insightful information. A numerical problem is analyzed to illustrate the effectiveness of the procedure.     

An Empirical Analysis of Handoff Performance for SIP,Mobile IP,and SCTP Protocols

Over the last decade, we have witnessed a growing interest in the design and deployment of various network architectures and protocols aimed at supporting mobile users as they move across different types of networks. One of the goals of these emerging network solutions is to provide uninterrupted, seamless connectivity to mobile users giving them the ability to access information anywhere, anytime. Handoff management, an important component of mobility management, is crucial in enabling such seamless mobility across heterogeneous network infrastructures. In this work, we investigate the handoff performance of three of the most widely used mobility protocols namely, Mobile IP, Session Initiation Protocol (SIP), and Stream Control Transmission Protocol (SCTP). Our empirical handoff tests were executed on an actual heterogeneous network testbed consisting of wired, wireless local area, and cellular networks using performance metrics such as handoff delay and handoff signaling time. Our empirical results reveal that Mobile IP yields the highest handoff delay among the three mobility protocols. In addition, we also found that SIP and SCTP yield 33 and 55% lower handoff delays respectively compared to Mobile IP.     

A secure enhanced privacy-preserving key agreement protocol for wireless mobile networks

The rapid proliferation of mobile networks has made security an important issue, particularly for transaction oriented applications. Recently, Jo et al. presented an efficient authentication protocol for wireless mobile networks and asserted that their proposed approach provides all known security functionalities including session key (SK) security under the assumption of the widely-accepted Canetti–Krawczyk (CK) model. We reviewed Jo et al.’s proposed roaming protocol and we demonstrate that it fails to provide the SK-security under the CK-adversary setting. We then propose an enhancement to Jo et al.’s roaming protocol to address the security drawback found in Jo et al.’s protocol. In the enhanced roaming protocol, we achieve the SK-security along with reduced computation, communication and storage costs. We also simulate the enhanced roaming protocol using NS2 for end-to-end delay and network throughput, and the simulation results obtained demonstrate the efficiency of our protocol.     

Optimal evacuation planning using staging and routing

Evacuation is an important disaster management tool. Evacuating a large region by automobile (the most commonly used mode) is a difficult task, especially as high levels of traffic congestion often form. This paper studies the use of demand-based strategies, specifically, the staging and routing of evacuees. These strategies attempt to manage demand in order to reduce or eliminate congestion. A strategic mixed-integer programming planning model that accounts for evacuation dynamics and congestion is used to study these strategies. The strategies adopted incorporate different evacuee types based on destination requirements and shelter capacity restrictions. The main objective studied is to minimize the network clearance time. We examine the structure of optimal strategies, yielding insights into the use of staging and routing in evacuation management. These insights are then used to develop effective solution procedures. To demonstrate the efficacy of the proposed solution technique, we provide computational experience using a large realistic example based on Virginia Beach.     

Set partitioning and packing versus assignment formulations for subassembly matching problems

This paper addresses alternative formulations and model enhancements for two combinatorial optimization problems that arise in subassembly matching problems. The first problem seeks to minimize the total deviation in certain quality characteristics for the resulting final products from a vector of target values, whereas the second aims at maximizing the throughput under specified tolerance restrictions. We propose set partitioning and packing models in concert with a specialized column generation (CG) procedure that significantly outperform alternative assignment-based formulations presented in the literature, even when the latter are enhanced via tailored symmetry-defeating strategies. In particular, we emphasize the critical importance of incorporating a complementary CG feature to consistently produce near-optimal solutions to the proposed set partitioning and packing models. Extensive computational results are presented to demonstrate the relative effectiveness of the different proposed modelling and algorithmic strategies.     

A real-time video quality estimator for emerging wireless multimedia systems

Wireless Mesh Networks (WMNs) are increasingly deployed to enable thousands of users to share, create, and access live video streaming with different characteristics and content, such as video surveillance and football matches. In this context, there is a need for new mechanisms for assessing the quality level of videos because operators are seeking to control their delivery process and optimize their network resources, while increasing the user’s satisfaction. However, the development of in-service and non-intrusive Quality of Experience assessment schemes for real-time Internet videos with different complexity and motion levels, Group of Picture lengths, and characteristics, remains a significant challenge. To address this issue, this article proposes a non-intrusive parametric real-time video quality estimator, called MultiQoE that correlates wireless networks’ impairments, videos’ characteristics, and users’ perception into a predicted Mean Opinion Score. An instance of MultiQoE was implemented in WMNs and performance evaluation results demonstrate the efficiency and accuracy of MultiQoE in predicting the user’s perception of live video streaming services when compared to subjective, objective, and well-known parametric solutions.