• Proposed an optimization-driven resource orchestration algorithm that enhances admission control and ensures Quality of Service (QoS) in SDN-based network slicing. • Introduced a Partial Admission Control (PAC) strategy, dynamically allocating network resources based on priority and real-time availability, addressing the limitations of rigid binary admission models. Efficient resource orchestration is essential for ensuring high Quality of Service (QoS) and reliability in Software-defined Networks (SDNs). This paper introduces an optimization-based algorithm that integrates Lagrangian Relaxation (LR) and Queueing Theory to enhance admission control and priority scheduling in SDNs. The proposed approach overcomes the limitations of traditional binary admission control methods by enabling Partial Admission Control (PAC), which allows more flexible resource allocation. The system’s performance is significantly improved through the use of non-preemptive and preemptive priority scheduling, while LR techniques effectively manage complex network conditions. Specifically, the proposed Bisection-Search (B-S) heuristic leverages the Lagrangian multipliers generated during the optimization process to intelligently guide resource allocation, consistently producing high-quality feasible solutions ( Z primal ). These solutions are validated against the theoretical bound ( Z LR ) provided by the LR method, demonstrating a provably small duality gap. The proposed algorithm is evaluated through extensive simulations across diverse network scales, traffic loads, and delay constraints, demonstrating substantial improvements in network performance and service differentiation. These results provide a comprehensive analysis of the performance envelope of the proposed framework, highlighting the trade-offs between solution quality, computational complexity, and network scale. The study offers an adaptive and mathematically grounded solution, demonstrating its effectiveness in complex, high-contention networking environments.

Biometric recognition plays an increasingly pivotal role in cybersecurity, where the CIA triad, Confidentiality, Integrity, and Availability, forms the cornerstone of information security, with authentication as a critical yet challenging component. This paper presents the Biometric Multi-modal Authentication System using Geometric Programming (BMMA-GPT), tailored for deployment in Fast IDentity Online (FIDO/FIDO2)-enabled environments and Zero Trust Architectures (ZTA). The system employs a dual-threshold mechanism integrated with Defense-in-Depth (DiD) strategies to simultaneously enhance accuracy, efficiency, and security. The underlying optimization problem is formulated as a mathematical programming task and reformulated into a Geometric Programming (GP) model to efficiently compute optimal biometric permutations and verification thresholds under constrained estimation errors. BMMA-GPT enables the flexible integration of multiple biometric modalities, allowing dynamic adjustments to meet both individual user profiles and organizational security requirements. It achieves a high Area Under Curve (AUC) of approximately 0.99 while maintaining authentication latency under 1.5 seconds. This design supports Chief Information Security Officers (CISOs) in configuring tailored authentication processes with minimal computational cost, enhancing resilience against spoofing attacks and ensuring seamless user experience. By aligning biometric verification with DiD principles and GP-based optimization, the proposed framework offers a scalable and robust solution for identity authentication in complex digital ecosystems.

This paper tackles key challenges in Software-Defined Networking (SDN) by proposing a novel approach for optimizing resource allocation and dynamic priority assignment using OpenFlow’s priority field. The proposed Lagrangian relaxation (LR)-based algorithms significantly reduces network delay, achieving performance management with dynamic priority levels while demonstrating adaptability and efficiency in a sliced network. The algorithms’ effectiveness were validated through computational experiments, highlighting the strong potential for QoS management across diverse industries. Compared to the Same Priority baseline, the proposed methods: RPA, AP–1, and AP–2, exhibited notable performance improvements, particularly under strict delay constraints. For future applications, the study recommends expanding the algorithm to handle larger networks, integrating it with artificial intelligence technologies for proactive resource optimization. Additionally, the proposed methods lay a solid foundation for addressing the unique demands of 6G networks, particularly in areas such as base station mobility (Low-Earth Orbit, LEO), ultra-low latency, and multi-path transmission strategies.

Hepatocellular carcinoma (HCC), the most common type of liver cancer, poses significant challenges in detection and diagnosis. Medical imaging, especially computed tomography (CT), is pivotal in non-invasively identifying this disease, requiring substantial expertise for interpretation. This research introduces an innovative strategy that integrates two-dimensional (2D) and three-dimensional (3D) deep learning models within a federated learning (FL) framework for precise segmentation of liver and tumor regions in medical images. The study utilized 131 CT scans from the Liver Tumor Segmentation (LiTS) challenge and demonstrated the superior efficiency and accuracy of the proposed Hybrid-ResUNet model with a Dice score of 0.9433 and an AUC of 0.9965 compared to ResNet and EfficientNet models. This FL approach is beneficial for conducting large-scale clinical trials while safeguarding patient privacy across healthcare settings. It facilitates active engagement in problem-solving, data collection, model development, and refinement. The study also addresses data imbalances in the FL context, showing resilience and highlighting local models' robust performance. Future research will concentrate on refining federated learning algorithms and their incorporation into the continuous implementation and deployment (CI/CD) processes in AI system operations, emphasizing the dynamic involvement of clients. We recommend a collaborative human-AI endeavor to enhance feature extraction and knowledge transfer. These improvements are intended to boost equitable and efficient data collaboration across various sectors in practical scenarios, offering a crucial guide for forthcoming research in medical AI.

A distributed coordination function is a serial fundamental media access control (MAC) mechanism of the IEEE 802.11 wireless network standards for accessing a medium and reducing the probability of collisions. Before sending data, each sender must check whether the medium is available. However, asymmetric detection and collision-avoidance mechanisms create transmission starvation problems. Hence, this paper addresses starvation problems to improve the quality of service in multihop wireless networks by adapting the transmission power range and carrier-sense threshold to alleviate starvation problems and to improve system performance. The problem is modelled as a mathematical formulation, and a Lagrangian relaxation (LR) approach is applied to obtain the approximation solution. The performance of the proposed algorithm is verified by applying it to several simulated starvation-avoidance routing problems. The results show that the proposed algorithm can near-optimally solve these problems, with an average lower bound-upper bound gap of 12.4%.

Wi-Fi wireless communication has become a basic service in public areas. However, the quality of service (QoS) might be inadequate in some areas because of the following influential factors: 1) the limited number of non-overlapping channels, 2) the interference caused by unplanned deployment and mobility, 3) the rapidly changing distribution of customers, and 4) access point (AP) failures. These factors result in non-uniform network traffic distribution and unavailability of service in some areas. Hence, this study focused on addressing the problems of AP failure and interference. We propose a self-healing algorithm to provide seamless and reliable service despite AP failures. The proposed water ripple algorithm maximizes the minimum delay difference, which is defined as the difference between transmission delay and tolerable delay, to satisfy requirements of multiple users simultaneously. Variable transmission power ranges (which involve cell breathing method types) and association management are adjusted to minimize the number of out-of-service mobile devices (MDs). Thus, fair allocation of resources to users and adequate QoS are satisfied.

Wireless Sensor Networks (WSNs), which are connected by sensor nodes with wireless communication techniques, are used to collect, process, and transmit the various types of environmental data, such as temperature, fire and smoke detectors, CO gas, humidity, pressure, and video-based data. The network lifetime is limited due to sensors are equipped with batteries. The measurement uncertainties and detection faults lead higher power consumption by retransmissions due to event detection error. These two factors influence with each other. In this study, there are two indicators are introduced for detection errors, false positive (FP) and false negative (FN) to evaluate a detection-based sensor network. For operation perspectives, three models are addressed to near-optimize the network lifetime and detection errors. Linear-and non-linear mathematical planning problems are formulated as (1) to minimize event FP rate subject to FN constraints, (2) to minimize the network energy consumption subject to detection accuracy requirements, turning sensor ON/OFF decisions, the required number of voting nodes, and given FP/FN constraints, and (3) to extend from the previous model as a planning problem for various types of sensor nodes deployed with diverse FP/FN characteristics and costs. An integer programming (IP) tool, LINGO, is adopted to solve the problems with computational experiments on several situations. The experimental results show that the objectives can be achieved, lots of useful hints or configurations can be applied for system implementations to improve system performance efficiently and effectively.

Wi-Fi wireless communication has become a basic service in public areas. But the quality is not stable due to the factors that are influenced by 1) a limited number of channels results in access interference, 2) various transmission ranges, carrier sensing and hidden terminal starvation problems, and 3) the barriers reduce the quality of transmissions. This work aims to explore and analyze the factors to show the level of performance effect on various transmission ranges of access points. Accordingly, this study designs several simulation cases to evaluate whether a small cell size can provide high performance co-existing with a large cell size by controlling the effect of the sensing ranges, transmission ranges, traffic types, data rates, and packet sizes. Network Simulation 3 (NS3) tool is used to implement the simulation cases and compare the results. We discussed our findings on these factors that affect the levels of starvation caused by the various signal ranges.

Abstract Multicast Broadcast Service (MBS) applications can efficiently reduce the usage of network resources, still providing mobile users with real‐time high‐quality content. MBS capabilities are usually implemented by using a single frequency network; moreover, new features, such as connection identifier for broadcast/multicast messages and other MBS‐enabled descriptors, are added to cope with already existent entities and services. With the intention to optimize performances and verify the on‐field feasibility, we propose an MBS approach to Orthogonal Frequency Division Multiple Access systems based on superposition coding (SPC). Because MBS features have a large impact in the architectural design of the network protocols, an integrated framework is mandatory to speed up the system simulation, verification, and redesign steps. This paper shows the design of an experimental testbed for performance evaluation of SPC‐enabled physical (PHY) and medium access control (MAC) layers over Mobile WiMAX systems. In addition, it proposes some architectural modifications of the WiMAX protocols, by exploiting its core network capabilities. The experimental results obtained from the testbed confirm that augmented throughput capabilities can be achieved by SPC‐enabled PHY/MAC layers. However, to fully exploit the additional available throughput, an integrated framework must be adopted to evaluate the protocol modifications for the MBS‐enabled entities. Copyright © 2014 John Wiley & Sons, Ltd.

Service continuity is a critical issue in wireless networks. Unfortunately, jamming attacks seriously threatens the continuity of wireless networks. The open nature of wireless mediums makes it vulnerable to any wireless capable devices. There are only few researches address the issue of how the service providers should deploy its topology or allocate its resources to minimize the impact of jamming attacks launched by malicious attackers. In this paper, a mathematical model formulating an attack-defense scenario of the problem is proposed. The results show when deploying defense resources, considering hops from core node is more useful than link degree. With the advantage of simulations, the concept of incomplete information can be taken into account which though raises the difficulty of the problem, but makes the problem closer to reality.

In the process of standardization, whether the announcement of a standard represents a cause or an outcome, it is opportunity of the trend of standardization or achievement. The process of standardization is to understand "why" and "how" to explore the detailed outline of a time flow. From a long-term perspective, a standard is the milestone of the standardization process. On May 26th 2010, with the announcement of the Personal Data Protection Act in Taiwan, information security management (ISM) of the Personal Data Protection Act has received much attention from the public. This study is centered on the working items of standards announced by the International Organization for Standardization (ISO) and the ongoing information security management system (ISMS) standards and standardization in order to propose standards which comply with the ISMS of the Personal Data Protection Act and methods which increase implementation control measures.

Although enterprises make profits by satisfying customers' needs, which is most often facilitated by information systems and network infrastructures, it is difficult to keep the systems and the network components regularly operating without any downtime. As a result, it is an important and critical issue for the system administrator or defender to efficiently evaluate network survivability. In this paper, a network optimization problem of attacker and defender behavior is considered. Both actors utilize their resources: the attackers launching attacks try to maximize the damage of the network, while the defenders deploy resources on the nodes and recover the compromised nodes. This problem is considering with survivability with a metric, Degree of Disconnectivity (DOD), which is used to evaluate the damage level of the network. The Lagrangean Relaxation Method is then applied to obtain optimal solutions for the proposed problem.

In this paper, we study the relay station (RS) placement strategy in IEEE 802.16j WiMAX networks. Specifically, the impact of RS placement on IEEE 802.16j network performance is analyzed. A throughput maximization RS placement problem is mathematically formulated as a binary integer programming problem. We prove the NP-hardness of the formulated problem. To find the sub-optimal solution to the problem with huge input size, we propose an efficient near-optimal placement solution for IEEE 802.16j WiMAX networks. Simulations on the IEEE 802.16j network performance with our RS placement strategy are conducted. The throughput performance shows that with the deployment strategy we proposed, the IEEE 802.16j network capacity can be tremendously enhanced, especially when hotspots are present in the network.

In this paper, we consider the problem of minimizing attackers' success probability in a protected network subject to attacker profile/behavior constraints and defender resource/strategy constraints. Compared with previous research, the following two enhancements are made. First, we no longer assume that perfect knowledge regarding the network topology and defense resource allocation is fully available for attackers (a worst case scenario for the defender). Second, all combinations of attacker classes can be considered, where each attacker class may be associated with any number of attributes, including ratio, intelligence/experience level, available attack resource and sophisticated attack strategies. The problem is modeled as a generic mathematical programming problem, and a novel two-phase solution approach, which well combines mathematical programming and simulation techniques, is proposed. More specifically, in the “Evaluation Phase”, efficient and effective simulations are conducted to evaluate the effectiveness of the current defense policy; whereas, in the “Defense Policy Enhancement Phase”, specially-proposed and easy-to-collect information from the “Objective Function Evaluation Phase” is adopted to calculate gradients of the decision variables. From computational experiments on honeynet, applicability and effectiveness of the proposed framework and algorithm are clearly demonstrated.

There are two challenges for the frame-slotted ALOHA algorithms in radio-frequency identification (RFID). The first challenge is estimating unknown tag-set size accurately; the second challenge is improving the efficiency of the arbitration process so that it uses less time slots to read all tags. This study proposes estimation algorithm based on the Poisson distribution theory and identifies the overestimation phenomenon in full collision. Our novel anticollision algorithm alternates two distinct reading cycles for dividing and solving tags in collision groups. This makes it more efficient for a reader to identify all tags within a small number of time slots.

Abstract Although limiting the number of backhauls, specifically chosen transit access points (TAPs) that forward traffic from other TAPs, reduces the overall costs of a wireless mesh network (WMN), an egress bottleneck is induced, which aggregates traffic and limits the bandwidth. To avoid such problems while working to minimize budgetary expenses, we balanced traffic flow on ‘to‐be‐determined’ backhauls and adjacent links, a mixed nonlinear‐and integer‐programming problem that minimizes the aggregated flow subject to budget, backhaul assignment, top‐level load‐balanced routing, and link capacity constraints. Two algorithms are proposed, weighted backhaul assignment (WBA) and greedy load‐balanced routing (GLBR), that operate in conjunction with Lagrangean relaxation (LR), used for constructing LR‐based heuristics and also as a means of quantification and evaluation of the proposed algorithms. Experiment results show that the proposed algorithms achieve near‐optimization, outperforming related solutions. Copyright © 2008 John Wiley & Sons, Ltd.

It is not possible to ensure that a network is absolutely secure. Therefore, network operators must continually change their defense strategies to counter attackers who constantly seek new ways to compromise networks. However, as defense resources are limited, it is essential that network operators devise effective resource allocation strategies to maximize the survival time of critical/core nodes under attack. In this paper, the problem of effective resource allocation is analyzed as a mixed, nonlinear, integer programming optimization problem. To solve this complex problem, we propose an effective solution approach based on Lagrangean relaxation and the subgradient method. The efficiency and effectiveness of the proposed heuristic are evaluated by computational experiments.

The issue of information security has attracted increasing attention in recent years. In network attack and defense scenarios, attackers and defenders constantly change their respective strategies. Given the importance of improving information security, a growing number of researchers are now focusing on how to combine the concepts of network survivability and protection against malicious attacks. As defense resources are limited, we propose effective resource allocation strategies that maximize an attacker's costs and minimize the probability that the "core node" of a network will be compromised, thereby improving its protection. The two problems are analyzed as a mixed, nonlinear, integer programming optimization problem. The solution approach is based on the Lagrangean relaxation method, which solves this complicated problem effectively. We also evaluate the survivability of real networks, such as scale-free networks

The nature of wireless sensor networks make them suitable for a great variety of applications, especially over wide areas, or in remote or hostile locations; however, such environments make battery capacity an especially important concern, where replacing or recharging of batteries is in- feasible for one reason or another. Battery capacity restrictions on highly energy-constrained sensor networks can be mitigated, by adopting data-aggregation techniques and by managing the scheduling of nodes. These effectively reduce the overall amount of data transmitted, thereby conserving energy. In this paper, we address the construction of energy-efficient data-aggregation trees, an NP-problem, in different rounds of communication, seeking to maximize the lifetime of heterogeneous sensor networks. This problem is subject to constraints on such networks: battery capacity, data-sensing scheduling, and round calculation. We derive a near-optimal primal feasible solution using Lagrangean relaxation. The experimental results show that our proposed algorithm outperforms similar algorithms.

The lifetime of a network, dependent upon battery capacity and energy consumption efficiency, plays an important role in wireless sensor networks. In this paper, the reduction of energy consumption is investigated by the considerations of the effects of cluster-based data aggregation routing in conjunction with well-scheduled and dynamic power range. Modeling power consumption as a mixed integer- and nonlinear-programming problem, the objective function provides the basis by which the total energy consumption is minimized. The problem of cluster construction and data aggregation trees were proven NP- complete. Thus, we proposed heuristics for cluster construction (i.e., AvgEnergy and MaxNumS) and data aggregation routing (i.e., CDAR). We also propose a duty cycle scheduling scheme and dynamic radius to ensure the total energy consumption is minimized. The experimental results show that the heuristic proposed above outperforms other modified existing algorithms.

Recharging the batteries of a moribund sensor deployed as part of a wireless sensor network is often infeasible due to logistical considerations. With the purpose of prolonging sensor lifetime in such data-centric wireless sensor networks and with emphasis on TDMA-based routing and the efficient scheduling of sensor activities, we propose a mixed-integer nonlinear programming mathematical model, the objective of which is to minimize the total energy consumed by nodes and encompasses dynamic power range, collision free transmission, routing paths, and data aggregation tree constraints. Performing Lagrangean relaxation, we find a near-optimal solution and verify that our proposed algorithm is energy efficient and bounds latency within a reasonable range. Our experiment results confirm improvement over data aggregation algorithms.

Multigranular optical WDM network aims to reduce network cost by grouping multiple wavelengths and then switching those wavelengths together at waveband or fiber levels. To configure such multi-granular network, we have two choices-homogeneous network and heterogeneous network. The former applies only a single type of optical cross connect (OXC) while the latter allows different types of OXCs. Due to the demands varies and change asymmetrically geographically, networks with heterogeneous OXC nodes is especially suitable for placing best switching types at different location. In this paper, we aim at the design of an algorithm to solve the network planning problem in optical network with heterogeneous multi- granularity OXCs. The planning program determines not only the switching granularity for each node but also determine the routing and wavelength assignments to satisfy the given demands. The contributions of the paper are four folded. First, we propose a graph model to represent the OXC node. The transformed graph simplifies the representation of node structure and helps to model the problem. Secondly, we propose a mathematical formulation to model the network planning problem as an ILP problem. Thirdly, a Lagrangean relaxation based heuristic algorithm is proposed to obtain a near optimal solution. Fourthly, we studied the impact of waveband size on network cost. This work reveals that the waveband size plays a crucial factor. The proposed algorithms can determine the optimal number of waveband size.

In consideration of the reader collision problem in radio frequency identification (RFID) networks, we present an algorithm that deploys RFID reader networks so that they are flexible and efficient. We formulate the deployment issue as 0/1 integer programming problem, and propose a simulated annealing-based heuristic algorithm to solve it.

Since the 9/11 terrorist attacks, the effective and efficient protection of critical information infrastructures has become an even more important issue. To enhance network survivability, a network operator needs to invest a fixed amount of budget and distribute it properly. However, a potential attacker always adjust his attack strategies to compromise a network at minimal cost, if he knows the resource allocation strategy of the network operator. In this paper, we first evaluate the survivability of a given network under two different metrics; that is, we assess the minimal attack cost incurred by an attacker. The two survivability metrics are assumed to be the connectivity of at least one given critical origin-destination pair (OD pair) and that of all given critical OD pairs. We then analyze the problem with two optimization-based models, in which the problem structure is, by nature, a mixed integer programming problem.

Abstract —Public wireless local area networks (PWLAN), which provide last-mile connectivity to the Internet, are popular worldwide, especially in heavily populated cities. Traditional ad hoc shortest path routing algorithms, such as AODV and DSR, focus on minimum hops that cause traffic to concentrate on some TAPs, while others are light. Thus, the major issue addressed this paper is how to cluster backbone mesh networks efficiently so that routing is concentrated on given gateways. We formulate the problem as an integer programming problem with minimal routing traffic as the objective function, subject to the top load balancing and link capacity. We propose a greedy algorithm, called Greedy Load Balancing Routing (GLBR), to solve this problem and evaluate it by the Lagrangian Relaxation approach to quantify the objective value correctly. The experimental results show that the algorithm achieves near-optimization, and obtains a gap smaller than 5% and 10% in grid-based and random-based architectures, respectively.

Incorporating sensor nodes with data aggregation capability to transmit less data flow in wireless sensor networks could reduce the total energy consumption. However, the penalty from data retransmissions due to collision could jeopardize the advantages from data aggregation. In this paper, for the first time, we consider the energy consumption tradeoffs between the data aggregation and retransmission in wireless sensor network. By using the CSMA-CA MAC protocol, the retransmission energy consumption function is well formulated. We propose a rigorous non-linear mathematical formulation, where the objective function is to minimize the total energy consumption of data transmission subject to data aggregation tree and data retransmission. The solution approach is based on Lagrangean relaxation in conjunction with the optimization-based heuristics. From the computational experiments, it is shown that the proposed algorithms could construct more energy efficient data aggregation tree with MAC layer retransmission mechanism than existing data centric algorithms up to 93%.

In this paper, we intend to solve the problem of maximum-revenue multicast routing with a partial admission control mechanism for multirate multimedia distribution. Specifically, for a given network topology, a given link capacity, the destinations of a multicast group, and the bandwidth requirement of each destination, we attempt to find a feasible routing solution to maximize the revenue of the multicast trees. The partial admission control mechanism means that the admission policy of the multicast group is not based on a traditional "all or none" strategy. Instead it considers accepting of partial portions of destinations for the requested multicast group. Firstly, we model this problem as an optimization problem. Then, we propose a simple heuristic algorithm and an optimization based heuristic to solve this problem. The methodology taken for solving the problem is Lagrangean relaxation. Computational experiments have been performed on regular networks, random networks, and scale-free networks.

The network lifetime for wireless sensor network plays an important role to survivability. Thus, we indicate the importance of routing protocol to network lifetime, and model the expected retransmission time as a convex function with respect to aggregate flow on each sensor node. Thus we formulate the optimal energy-efficient routing as a non-linear min-max programming problem with convex product form, which can be optimally solved by optimal routing framework. Based on the optimal routing framework, we propose Lagrangean-based algorithm and primal optimal algorithm. By the combination of these two algorithms, we can optimally and efficiently get the routing assignment to maximize the network life in the sensor network. From experiments, we observe that when the optimal network lifetime increases as the number of sensor nodes increase. While the shortest path-based heuristic algorithm can only achieve about 48% network lifetime compared to our solution approach.

Due to varying wireless channel conditions, the IEEE 802.11 wireless local area network (WLAN) standard supports multiple modulation types to accommodate the tradeoff between data rate and bit error rate. In Heusse(2003), Rousseau, Berger-Sabbatel and Duda theoretically analyzed a performance anomaly when multi-rate stations with different modulation types exist in IEEE 802.11 WLANs. The performance anomaly is: the aggregate throughput of those stations transmitting at a higher data rate will dramatically degrade below the same level as that of those stations transmitting at a lower data rate. In this paper, we address the anomaly problem and formulate a nonlinear mixed integer programming problem to maximize the total aggregate throughput of all stations subject to that the channel occupancy times among the stations transmitting at different data rates are kept at a fairness ratio. With its aid, a single-hop WLAN can dynamically accommodate the resource access usage to maximize the system throughput in varying fading environments. We prove that the optimization problem is intractable and propose a heuristic solution based on a penalty function with gradient-based approach to solve it. We show the effectiveness of the approach via computational experiments and provide some useful guidelines to regulate the parameters needed for the approach.

Incorporating sensor nodes with data aggregation capability to transmit less data flow in wireless sensor networks could reduce the total energy consumption. This calls for the efficient and effective data-centric routing algorithm to facilitate this advantage. In this paper, we model the data-centric routing problem by a rigorous mixed integer and linear mathematical formulation where the objective function is to minimize the total transmission cost subject to multicast tree constraints. The solution approach is based on Lagrangean relaxation in conjunction with the optimization-based heuristics. From the computational experiments, it is shown that the proposed algorithm calculates a better solution than other existing heuristics with improvement ratio up to 169% for a network with 300 random generated nodes in five minutes of computational time.

In this paper, we develop a novel algorithm to deploy an energy-efficient wireless sensor network (WSN) for the target-location service that is one of the major applications of sensor networks. Such sensor network has to be designed to achieve complete coverage quality of surveillance and full discrimination for predetermined resolution on the sensor field. To extend lifetime of sensor network, the duplicate deployment approach is a simple and intuitive way. However, such approach will result in increasing too much deployment cost. In this paper, we propose a novel strategy to cope with the problem. We consider deploying K independent sets of sensors to monitoring the area in turn and locating the intruder together. With this strategy, the duty cycle of each sensor is only 1/K and the lifetime of the sensor network will be extended up to K times. Such sensor placement problem is a variant of the set K-cover problem, which is NP-complete. We formulate the problem as a 0/1 integer-programming problem. A Lagrangean relaxation based heuristic then is proposed for solving the optimization problem. The experimental results show that the proposed strategy gets a significant improvement in the lifetime of sensor network compared to the duplicate deployment approach under the deployment cost constraint. The proposed algorithm is highly effective in terms of the overall deployment cost. Furthermore, the algorithm is very efficient and scalable in terms of the solution time. I. INTRODUCTION The rapid growth in sensor technology and wireless com- munication has led to the development of wireless sensor networks (WSNs). A wireless sensor network comprises sev- eral sensors, sink nodes, and back-end systems. These tiny, low-cost, and low power sensors are deployed in an ad hoc manner in an interested area. These sensors collect physical information from the area, process and forward the information to the sink nodes. Afterward, the back-ends can obtain global views according to the information provided by the sink nodes

In this paper, we develop an algorithm to deploy an energy efficient sensor network such that it provides surveillance and target-positioning services. We consider to place K independent sets of sensors on a sensor field. These sets monitor the field in turn and work together when intrusion events occur. The lifetime of the sensor network is therefore prolonged up to K times. The problem is therefore a variant of the set K-cover problem, which is NP-complete. We formulate such sensor deployment problem, as a 0/1 integer programming problem. A simulated annealing based heuristic then is proposed for solving the optimization problem. The experimental results show that the proposed algorithm indicates a significant improvement in the sensor lifetime compared to the intuitive approach. Furthermore, the proposed algorithm is highly effective and efficient in terms of the overall deployment cost.

We study the problems of resource and performance management in channelized wireless networks. For identifying research issues systematically, we propose a research framework which consists of two modules: performance optimization and network servicing modules. For an in-service communication network, performance optimization module manages radio resources to ensure communication quality of service and optimize system performance. For channelized wireless system, the real-time issues of performance optimization are admission control, channel assignment, power control, and homing. The network servicing module is event-driven or a periodically resource augmentation plan, which alleviates the performance exceptions and optimizes long-term system revenue by using corrective mechanisms consisting of resource augmentation, channel reassignment, cell rearrangement, and rehoming issues. Under the consideration of generic sectorization and interference effects, we introduce several mathematical models for both modules and formulate the associated issues as combinatorial integer programming problems. By using the Lagrangean relaxation method, several efficient and effective algorithms are developed to deal with these NP-hard problems.

An essential issue in designing, operating and managing a modern network is to assure end-to-end quality-of-service (QoS) from users' perspective, and in the meantime to optimize a certain "average" performance objective from the system's perspective. We consider the problem of minimizing the average cross-network packet delay in virtual circuit networks subject to an end-to-end delay constraint for each origin-destination user pair. The problem is formulated as a multicommodity network flow problem with integer routing decision variables, where additional end-to-end delay constraints are considered. The difficulties of this problem result from the integrality nature and particularly the nonconvexity associated with the end-to-end delay constraints. The basic approach to the algorithm development is Lagrangean relaxation in conjunction with number of optimization-based heuristics. In the computational experiments, it is shown that the proposed algorithm calculates solutions which are within 1% and 3% of optimal solutions under lightly and heavily loaded conditions, respectively, in minutes of CPU time for networks with up to 26 nodes.

The problem of determining admission controls and a path for each admitted user pair (session) to satisfy user quality of service (QOS) requirements (required throughput, tolerable average cell delay, and tolerable cell loss probability) is considered. The problem is formulated as a nonlinear combinatorial optimization problem. The objective is the maximization of the total reward for the admitted sessions where the reward for each session reflects its priority. The emphasis is on developing a real-time distributed algorithm to determine path assignments and admission controls. In computational experiments, the proposed distributed algorithm is compared with the minimum hop algorithm on test networks with up to 61 nodes and 10000 macro sessions. The proposed algorithm achieved a 36% (on the average) improvement in the total reward over a minimum hop routing algorithm and heuristic admission control scheme in less than 1.5 s of CPU time using distributed computation.>

To size networks that support switched multimegabit data service (SMDS), one must determine how much additional capacity is needed and where it is needed so as to minimize the total capacity augmentation cost. Two combinatorial optimization problem formulations are considered and compared for their relative applicability and complexity. A solution procedure based on Lagrangean relaxation is proposed for one of the formulations. In computational experiments, the proposed algorithm determines solutions that are within a few percent of an optimal solution in minutes of CPU time for networks with 10-26 nodes. The proposed algorithm is compared with a most congested first (MCF) heuristic. For the test networks, it achieves up to 152% improvement in the total cost over the MCF heuristic.>

In this paper, the routine problem in virtual circuit networks is considered. In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. We consider the problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network. We consider the formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables. The emphasis of this work is to develop a distributed algorithm to solve this optimization problem. The basic approach is Lagrangean Relaxation. We introduce a new multiplier update rule which facilitates the solution of the nonlinear integer programming problem using distributed computation. In computational experiments, our proposed distributed algorithm determines solutions that are within 1% of an optimal solution in less than 2 minutes of CPU time for networks with 26 to 61 nodes. In addition, the proposed multiplier adjustment procedure provides better bounds and is less sensitive to the algorithm parameters than the subgradient method. An analysis of the communication delays of the control messages needed to support a distributed implementation is given. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract In virtual circuit networks, all the packets in a session are transmitted over exactly one path established between the origin and the destination. For each origin–destination pair, it is assumed that there are multiple sessions. We consider the problem of choosing a path for each session so as to minimize the average packet delay in the network. We formulate this problem as a nonlinear multicommodity flow problem with integer decision variables. An iterative scheme that is similar to local search is developed to solve this problem. In each iteration, we apply Lagrangean relaxation and a multiplier adjustment procedure to solve a restricted problem. We show that the Lagrangean dual problem can be solved exactly by solving a convex program. In computational experiments, our algorithm determines solutions that are within 1% of an optimal solution in minutes of CPU time for networks with 26–61 nodes. In addition, we show that our proposed algorithm is better both theoretically and computationally than K(0)‐ordering, single‐path routing, or round‐off Frank–Wolfe heuristics.

In virtual circuit networks, all of the packets in a session are transmitted over exactly one path established between the origin and the destination. The problem of choosing a path for each origin-destination pair so as to minimize the average number of packets in the network is considered here. The usual formulation of this problem as a nonlinear multicommodity flow problem with integer decision variables is considered. A distributed algorithm is developed to solve the optimization problem, using Lagrangean relaxation as the basic approach. A multiplier update technique is developed which facilitates the solution of the nonlinear integer programming problem using distributed computation.>