The Quasi‐Affine Transformation Evolutionary (QUATRE) algorithm is a swarm‐based collaborative optimization algorithm, which has drawn attention from researchers due to its simple structure, easy implementation, and powerful performance. However, it needs to be improved regarding the exploration, especially in the late stage of evolution, and the problem of easy falling into a local optimal solution. This paper proposes an improved algorithm named Quasi‐Affine Transformation Evolutionary with double excellent guidance (QUATRE‐DEG). The algorithm uses not only the global optimal solution but also the global suboptimal solution to guide the individual evolution. We establish a model to determine the guiding force by the distance between the global optimal position and the suboptimal position and propose a new mutation strategy through the double population structure. The optimization of population structure and the improvement of operation mechanisms bring more exploration for the algorithm. To optimize the algorithm, the experiments on parameter settings were made to determine the size of the subpopulation and to achieve a balance between exploration and development. The performance of QUATRE‐DEG algorithm is evaluated under CEC2013 and CEC2014 test suites. Through comparison and analysis with some ABC variants known for their strong exploration ability and advanced QUATRE variants, the competitiveness of the proposed QUATRE‐DEG algorithm is validated.

We propose and implement a novel positioning system, WalkieLokie, which directly calculates the relative position from a smart device to a target. The requirement of the target is simple: it is attached with a “dummy” acoustic speaker, which does not have any other rich capabilities, such as audio recording, communication, or computation. Hence, the proliferation of smart devices, together with the cheap accessory (e.g., dummy speaker) embedded in daily used items (e.g., smart clothes), paves the way for WalkieLokie applications. WalkieLokie leverages the walking motion for locating an acoustic speaker. The key insight is that the distance between the user and the speaker varies in real time when the user walks, and the pattern of the variance implies the relative position. We design a novel algorithm to estimate the position and signal processing methods to support accurate positioning. The experiment results show that the mean errors of ranging and direction estimation are 0.63 m and 2.46°, respectively. Extensive experiments conducted in noisy environments validate the robustness of WalkieLokie.

In this paper, we propose and implement WalkieLokie, a novel acoustic-based relative positioning system. WalkieLokie facilitates a multitude of Augmented Reality (AR) applications: users with smart devices can passively acquire surrounding information in real time, similar to the commercial AR system Wikitude; the surrounding presenters, who want to share information or introduce themselves, can actively launch the function on demand. The key rational of WalkieLokie is that a user can perceive a series of spatial-related acoustic signals emitted from a presenter, which depicts the relation position between the user and the presenter. The proliferation of smart devices, together with the cheap accessory (e.g., dummy speaker) embedded in daily used items (e.g., smart clothes), paves the way for WalkieLokie applications. We design a novel algorithm to estimate the position and signal processing methods to support accurate positioning. The experiment results show that the mean error of ranging and direction estimation is 0.63m and 2.46 degrees respectively. Extensive experiments conducted in noisy environments validate the robustness of WalkieLokie.

Interference management is one of the most important issues in the heterogeneous cellular networks (HetNet) with macro and pico cells. The enhanced inter cell interference coordination (eICIC) has been proposed to protect downlink pico cell transmissions by mitigating interference from neighboring macro cells. The adaptive eICIC configuration problem is studied in this paper to adjust the parameters including the ratio of Almost Blank Subframes (ABS) and the bias of cell range expansion (RE). We formulate the problem as a general form consensus problem with regularization, and solve the problem by providing an efficient distributed optimization framework. Our algorithm is based on the alternating direction method of multipliers (ADMM) in which the solutions to local subproblems on each macro cell and pico cell are coordinated to find a solution to the global problem for the whole network. We also propose the dynamic programming based algorithms to solve the local subproblems on macro cell or pico cell. The simulation results demonstrate the efficiency of the proposed algorithm compared with existing approaches, and verify the convergence properties of the proposed algorithm.

Scalable video coding (SVC) is attractive technology for multicasting video to users with different available transmission capacities. In this paper, we investigate the joint optimization of resource allocation and user association problems for SVC multicast over heterogeous cellular networks (HetNet) employing the schemes of cell range expansion (RE) and almost blank subframe (ABS). We solve the joint optimization problem by decoupling it into two problems, namely, resource allocation (RA) subproblem and user association (UA) master problem. For the RA subproblem, we propose a dynamic programming based algorithm to optimally set the transmission profile. For the UA master problem, we propose a similarity-based negotiation protocol (SBNP) based algorithm to obtain the Pareto-optimal range expansion bias. The simulation results demonstrate the efficiency of these algorithms.

This paper investigates the joint optimization problem of user scheduling, user association, and resource partition in heterogeneous cellular networks (HetNet) with a general concave utility function used as the performance metric. We formulate the joint optimization problem, and decouple the problem into three sub problems. After proving the sub problems belong to the set of problems that maximizes a monotone sub modular set function with mastoid constraint, we solve them by the proposed greedy based algorithms with theoretical approximation factors. Extensive simulation results demonstrate the efficiency of the proposed algorithms in terms of system utility. In addition, we evaluate some assumptions and results in the related work to show their impacts and correctness.

Device-to-device (D2D) communication underlaying a cellular infrastructure has been proposed as a means of facilitating rich local services and offloading the base station traffic. However, D2D communication presents a challenge in radio resource management due to the potential interference it may cause to the cellular network. In this paper, the joint optimization problem of D2D mode selection, modulation and coding schemes (MCSs) assignment, radio resources and power allocation is formulated to minimize the overall power consumption under minimum required rate guarantee. The problem is decoupled into two sub-problems which are solved by Lagrangian relaxation and tabu search methods, respectively. Simulation results show its performance superiority over other schemes, especially in the scenarios with high required rate and limited resources.

Collaborative content storing and requesting are emerging solutions to Video-on-Demand (VoD) systems challenged by the explosive growth of online video demand. By exploiting the collaboration among the serving nodes in a VoD system, the new solutions dramatically increase the system capacity. In this work, we focus on the in-system collaborative request routing problem. Together with the video-adaptation techniques, we optimize the aggregate utility of end users while keeping the maximum link congestion under a given upper bound. We prove that the formulated problem is NP-hard, and solve it in two phases: a rate-selection phase and a fixed-rate routing phase. Afterwards, we convert the raw output of the proposed algorithm to a hop-by-hop routing-decision protocol which can be easily implemented in most existing routers. Numerical results show that our solution to the fixed-rate routing problem supports up to 60% more traffic than existing shortest-path algorithm. With joint video adaptation, our algorithm for optimizing utility outperforms the simple greedy method up to 18%.

This paper exploits sink mobility to prolong the network lifetime in wireless sensor networks where the information delay caused by moving the sink should be bounded. Due to the combinational complexity of this problem, most previous proposals focus on heuristics and provable optimal algorithms remain unknown. In this paper, we build a unified framework for analyzing this joint sink mobility, routing, delay, and so on. We discuss the induced subproblems and present efficient solutions for them. Then, we generalize these solutions and propose a polynomial-time optimal algorithm for the origin problem. In simulations, we show the benefits of involving a mobile sink and the impact of network parameters (e.g., the number of sensors, the delay bound, etc.) on the network lifetime. Furthermore, we study the effects of different trajectories of the sink and provide important insights for designing mobility schemes in real-world mobile WNNs.

ABSTRACT This paper deals with the partial target coverage problem in wireless sensor networks under a novel coverage model. The most commonly used method in previous literature on the target coverage problem is to divide continuous time into discrete slots of different lengths, each of which is dominated by a subset of sensors while setting all the other sensors into the sleep state to save energy. This method, however, suffers from shortcomings such as high computational complexity and no performance bound. We showed that the partial target coverage problem can be optimally solved in polynomial time. First, we built a linear programming formulation, which considers the total time that a sensor spends on covering targets, in order to obtain a lifetime upper bound. Based on the information derived in previous formulation, we developed a sensor assignment algorithm to seek an optimal schedule meeting the lifetime upper bound. A formal proof of optimality was provided. We compared the proposed algorithm with the well‐known column generation algorithm and showed that the proposed algorithm significantly improves performance in terms of computational time. Experiments were conducted to study the impact of different network parameters on the network lifetime, and their results led us to several interesting insights. Copyright © 2011 John Wiley & Sons, Ltd.

The resource allocation problem to support scalable-video multicast for wireless relay networks is complex due to the existence of the relay station. In this paper, we consider the resource allocation for SVC multicast over two-hop wireless relay networks to maximize the total system utility of all users where the system utility can be a general non-negative, non-decreasing function. We model the problem in three-layer structure (choice elements, action elements, and user elements) to cope with the joint dependency and overlapping phenomena. We formulate the problem as Cascaded Coverage Problem (CCP) and propose a greedy algorithm with polynomial time complexity. Simulation results show that our algorithm keeps good performance as compared with the optimal result. We also evaluate the influence of different user distribution types and the number of relay stations.

This paper exploits sink mobility to prolong the network lifetime in wireless sensor networks (WSNs) where the information delay caused by moving the sink should be bounded. We build a unified framework for analyzing this joint sink mobility and routing problem. We offer a mathematical modeling that is general and captures diversified issues, e.g. sink mobility, routing, delay, etc. We discuss the induced subproblems and present efficient solutions for them. Then, we generalize these solutions and propose a polynomial-time optimal algorithm for the origin problem. In simulations, we show the benefits of involving a mobile sink. We also show that the impact of the delay bound on the network lifetime.

Orthogonal frequency division multiplexing (OFDM) is regarded as a promising technique for the next generation wireless networks. In OFDM system, transmitter can provide high data rates by dividing channels into multiple orthogonal subcarriers and then allocates them to different users. But in the field of multicast, the conventional method ignores the differences of the channel condition between the users and therefore forces the modulation be adjusted to serve the worst user. The unique contribution of our work is to maximize the total throughput in a time efficient manner. In this paper, we propose a dynamic-programming-based algorithm to find the maximum capacity of system in a global manner after partitioning the available power into schedulable equal pieces. Experimental results demonstrate the effectiveness and efficiency of the proposed algorithm, the system throughput gap between the proposed dynamic-programming-based algorithm and the optimal algorithm is within about 2%, and significantly outperform the lowest channel gain method as well as the previous works.

Future 4G cellular networks are featured with high data rates and improved coverage, which will enable real-time video multicast and broadcast services. Scalable video coding with different modulation and coding schemes (MCSs) applied to different video layers is very appropriate for wireless multicast services because it can provide different video quality to different users according to their channel conditions and light-weight feedback on how many packets they have received. It is important to choose an appropriate MCS for each layer, decide how many parity packets in one layer should be transmitted, and determine the resources allocated to multiple video sessions to apply scalable video coding to wireless multicast streaming. This paper proposes an optimal algorithm that finds the optimal total system utility of all users where the utility can be a generic nonnegative, non-decreasing function of the received rate. The results from simulations revealed that our algorithm offer significant improvements to video quality over an optimal algorithm without feedback from users and a naïve algorithm especially in scenarios with multiple video session and limited resources.

Video multicast over wireless networks has its own challenges when facing the heterogeneity of networks and end-user capabilities, along with packet losses. Scalable video coding using different modulation and coding schemes (MCSs) applied to different video layers can provide different video qualities to different users according to their channel conditions. A layered hybrid NC/ARQ scheme is proposed in this paper to handle packet losses together with a structure network coding (SNC) technique to encode the SVC stream. It is important to choose an appropriate MCS for each layer, decide how many SNC packets in one layer should be transmitted, and determine the resources allocated to multiple video sessions to apply scalable video coding to wireless multicast streaming. We prove that such a resource allocation problem is NP-hard and propose an optimal algorithm with a pseudo-polynomial run time under a reasonable assumption. We also discuss the phenomenon of unexpected packet losses caused degradation of the layered hybrid NC/ARQ schemes in a high packet loss ratio environment, and propose a solution for overcoming such a problem. Our algorithm can attain the optimal transmission configuration for maximizing the expected utility for all receivers. The results from simulations revealed that our algorithm offers significant improvements to the video quality over an optimal algorithm without needing feedback from the receivers and an algorithm using a layered hybrid FEC/ARQ scheme, and it has the outstanding ability to combat unexpected packet losses.

Future mobile broadband networks are characterized with high data rate and improved coverage, which will enable real-time video multicast and broadcast services. Scalable video coding (SVC), combined with adaptive modulation and coding schemes (MCS) and wireless multicast, provides an excellent solution for streaming video to heterogeneous wireless devices. By choosing different MCSs for different video layers, SVC can provide good video quality to users in good channel conditions while maintaining basic video quality for users in bad channel conditions. A key issue to apply SVC to wireless multicast streaming is to choose appropriate MCS for each video layer and to determine the optimal resource allocation among multiple video sessions. We formulate this problem as total utility maximization, subject to the constraint of available radio resources. We prove that the formulated problem is NP-hard and propose an optimal, two-step dynamic programming solution with pseudo-polynomial time complexity. Simulation results show that our algorithm offers significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, especially in the scenarios with multiple real video sequences and limited radio resources.

Using beamforming antennas to improve wireless multicast transmissions has received considerable attention recently. A recent work proposes to partition all single-lobe beams into groups and to form composite multilobe beam patterns to transmit multicast traffic. Depending on how the power is split among the individual beams constituting a composite beam pattern, two power models are considered: 1) equal power split (EQP), and 2) asymmetric power split (ASP). This paper revisits the key challenge-beam partitioning in the beamforming-multicast problem-and makes significant progress in both algorithmic and analytic aspects of the problem. Under EQP, we propose a low-complexity optimal algorithm based on dynamic programming. Under ASP, we prove that it is NP-hard to have (3/2-ϵ)-approximation algorithm for any ϵ >; 0. For discrete rate functions under ASP, we develop an Asymptotic Polynomial-Time Approximation Scheme (APTAS), an asymptotic (3/2+ β)-approximation solution (where β ≥ 0 depends on the wireless technology), and an asymptotic 2-approximation solution to the problem by relating the problem to a generalized version of the bin-packing problem. In retrospect, we also obtain an asymptotic 2-approximation solution for the generalized bin-packing problem, which is of independent interest. For continuous rate functions under ASP, we develop sufficient conditions under which the optimal number of composite beams is 1,K, and arbitrary, respectively, whereKis the total number of single-lobe beams. Both experimental results and simulations based on real-world channel measurements corroborate our analytical results by showing significant improvement compared to state-of-the-art algorithms.

As a promising way in surveillance applications, wireless sensor networks (WSNs) often encounter the target coverage (TC) problem, i.e., scheduling energy-limited sensors to monitor physical targets to prolong the network lifetime. Due to the complexity of the problem (scheduling in time domain), previous proposals mainly focus on heuristics and provable optimal algorithms remain unknown. In this paper, we fill in the research blank by providing several theoretical results. First, we present a mathematical formulation and several investigations of the problem in time domain. Such time-related results provide fundamental understandings of the problem and serve as a basis. Second, we offer an upper bound on the network lifetime derived from the time-dependant formulation. The bound, which is solvable in polynomial-time, serves as a performance benchmark. Third, we verify the set cover-based method, which is widely used by previous studies, via a transformation of the problem from time to space domain. Lastly, we offer a specialized nonlinear column generation (CG) based approach to solve the problem in space domain optimally. Simulation results show that not only the bound is effective, but also the CG-based approach offers significant improvement on the network lifetime over a brutal search algorithm and a state-of-art heuristic.

Video multicast over broadband wireless networks suffers from packet losses induced by fading wireless channels and user heterogeneity in channel conditions within a multicast group. A promising solution to these problems is the use of layered hybrid FEC/ARQ for scalable video multicast. However, how to allocate the radio resources to multiple video layers and how to address the cross-layer combination of application layer hybrid FEC/ARQ and physical layer MCS (modulation and coding schemes) for each video layer, is not a trivial issue. We prove that this problem is NP-hard and propose an optimal Error-resilient Video Multicast (ERVM) framework in infrastructure-based broadband wireless networks. To avoid user heterogeneity and feedback implosion, we use a weighted designated user group to send light-weight feedback messages. The ERVM algorithm is based on the dynamic programming method with a pseudo-polynomial run time, and can get the optimal transmission configuration to maximize the expected utility for the designated user group, which is a probabilistic function of the received video rate. Simulation results show that our ERVM algorithm offers significant improvements over the conventional single-layer FEC/ARQ scheme and the layered FEC scheme. Furthermore, our weighted designated user group with light-weight and accurate feedbacks is better than other user feedback schemes.

Sink scheduling is shown to be a promising scheme in wireless sensor networks. However, previous approaches on this topic suffer from poor performance due to lack of joint considerations. Therefore, in this paper, we aim to fill in the research blank. First, we develop a novel notation Placement Pattern (PP) to bound time-varying routes with placement of sinks. This bounding technique transforms time-related constraints into pattern-based ones and allows us to formulate this optimization in pattern domain. If there is only one sink, we develop a polynomial time algorithm to solve it optimally. If there are multiple sinks, we develop a column generation based approach to solve it efficiently. Simulations not only demonstrate the efficiency of proposed algorithms but also substantiate the importance of sink mobility for energy-constrained sensor networks.

In this paper we investigate the issue of exploiting switched beamforming antennas to improve multicast transmission in wireless networks. Under the practical assumptions that different beams may have arbitrary overlapping patterns and that each user can receive data at different rates under different beams, we formulate the problem as minimizing the total multicast delay subject to the constraint that all users need to be covered. We prove that the problem is NP-hard and propose a greedy algorithm that achieves log(J) approximation guarantee where J is the number of clients. Measurements in both indoor and outdoor experiments validate our assumptions on the beamforming model. Trace-driven simulations based on these measurements show significant improvement over previous schemes and corroborate our analytical results.

Wireless multicast based video delivery is constrained by the user with the lowest channel quality within a multicast group. Beamforming increases the SINR at the clients thereby increasing the minimum channel quality among the users that form the multicast group. Thus it can be utilized to enhance the wireless multicast video transmission. In this paper, we investigate how to exploit switched beamforming antennas to improve wireless multicast based video transmission in indoor environments. The fundamental problem to be solved is the selection and scheduling of beams to be used to cover different subsets of users within the multicast group. We consider both multi-resolution videos and multi-layered videos and formulate the problem as maximizing the total utility of all multicast clients subject to a total delay constraint, where the utility is a general measure of video quality or user-satisfaction. We prove that it is NP-hard to have a (1-1/e+ε)-approximation solution to this problem for any ε >; 0, under both multi-resolution and multi-layered video models. For the multi-resolution video model, we develop a unified approximation algorithm with a parameter k that controls both the algorithm complexity and the approximation factor. For k = 0, 1, 2, 3, we prove that the proposed algorithm achieves an approximation guarantee close to 0.31, 0.38, 0.55, and 0.63, respectively. For the multi-layered video model, we propose a similar heuristic solution. The proposed algorithms are evaluated with both hypothetical video sequences and real video sequences using channel data collected in an indoor wireless testbed. Evaluation results show that the proposed algorithms have much better performance than naive multicast algorithms for scheduling the beams.

Using beamforming antennas to improve wireless multicast transmissions has received considerable attention recently. The work in proposes to partition all single-lobe beams into groups and to form composite multi-lobe beam patterns to transmit multicast traffic. The key challenge left is, how to partition the beams into multiple groups in order to minimize the total multicast delay. This work makes significant progress in both algorithmic and analytic aspects of the problem. We prove that, under the asymmetric power split (ASP) model, it is NP-hard to have (3/2 - ε)-approximation algorithm for any ε >; 0. We then develop an APTAS, an asymptotic (3/2 + β)-approximation solution (where β ≥ 0 depends on the wireless technology), and an asymptotic 2-approximation solution to the problem by relating the problem to a generalized version of the bin-packing problem. Extensive trace-driven simulations based on real-world channel measurements corroborate our analytical results by showing significant improvement compared to state of the art algorithms.

We address the optimal sink scheduling problem in wireless sensor networks (WSNs). The problem is inherently difficult since sink scheduling and data routing are tightly coupled. Previous approaches either have questionable performance due to no joint considerations, or are based on relaxed constraints. Our aim is to fill in this blank in the research. First, by discretizing continuous time, we develop a novel bound technique to connect time-varying routes with the placement of sinks. This bounding technique transforms time-related constraints into pattern-based ones and allows us to mathematically formulate this optimization in a pattern-based way. The complexity of directly solving this optimization is intractable; therefore, on the basis of column generation (CG), a computationally efficient algorithm is developed to reduce the complexity by decomposing the problem into sub-problems and iteratively solving them to approach optimality. Simulations demonstrate the efficiency of the algorithm and substantiate the importance of sink mobility in energy-constrained sensor networks.

Recently, sink deployment, in the form of deploying the sink among different sites so as to leverage traffic burden, is shown to be a promising scheme to save energy and prolong network lifetime in wireless sensor networks. For this paradigm, the choice of sink sites plays a critical role in the overall system performance. In this paper, we address the optimal deployment problem for the sink in wireless sensor networks, where routing issues are naturally involved. The major contribution of this paper is the development of an efficient grid-based algorithm to solve this problem. By dividing the continuous search space into a limited number of so-called communication intersections, computational complexity has been significantly reduced. A formal proof of optimality for this algorithm is given and several interesting properties have been revealed by theoretic analysis as well as experimental results.

Scalable video coding (SVC) and Adaptive Modulation and Coding (AMC) are two key techniques for video multicast in broadband wireless networks. They can improve the system performance by enhancing the wireless resource allocation schemes and assigning appropriate modulation and coding schemes (MCS) to different layers of scalable video sequences. We formulate the problem as maximizing the total system utility subject to the total resource constraint, where the utility of each user is a generic non-negative, non-decreasing function of received rate. We then propose a fast intra-session MCS assignment algorithm based on dynamic programming. This algorithm can be integrated with an existing inter-session resource allocation algorithm and applied to multi-session scenarios. Simulation results show that our algorithm achieves significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, and greatly reduces the running time in both single-session and multi-session scenarios compared to a former optimal algorithm.

Scalable video coding (SVC), together with adaptive modulation and coding (AMC), can improve wireless multicast streaming video by jointly performing radio resource allocation and modulation and coding scheme (MCS) selection. However, the existing schemes in the literature allocate radio resources for different video layers separately, which leads to a waste of radio resources. In this work, we introduce the notion of joint layer resource allocation which allows to jointly allocate resources to multiple video layers that are assigned the same MCS. We formulate this problem and prove it to be NP-hard. Then we develop a pseudo-polynomial algorithm that finds the optimal total system utility. Our algorithm assumes a very generic utility function and flexible video layer rates. To reduce the complexity of the algorithm, we also propose Fully Polynomial Time Approximation Schemes (FPTAS) for the same problem. Simulation results show that our optimal algorithm offers significant improvement on system utility over a previous optimal algorithm and a greedy algorithm both of which do not support joint layer resource allocation. The proposed approximation algorithm provides controllable tradeoff between performance and computational complexity and, with appropriately chosen parameters, it outperforms the greedy algorithm with 40% less running time.

This paper deals with the partial target coverage (PTC) problem in wireless sensor networks with the objective of optimizing network lifetime. We first build a linear programming formulation, which takes total time a sensor spends on covering some targets into consideration, in order to obtain a lifetime upper bound. Then, based on the information of this formulation, we develop a sensor assignment algorithm to seek an optimal time table meeting the lifetime upper bound. A formal proof of optimality is given. We compare the proposed algorithm with a state-of-the-art algorithm: column generation approach and show that the proposed algorithm significantly outperforms in terms of computational time. Experiments have been conducted to study the effect of network parameters on network lifetime and interesting insights have been offered.

The target coverage problem is one of the most fundamental challenges in wireless sensor networks. Due to the complexity of the problem (time-dependent network topology and coverage constraints), previous studies have mainly focused on heuristic algorithms and the theoretical bound remains unknown. In this paper, we aim to fill in this gap by providing fundamental results. First, we investigate the properties of a problem in time domain via an example topology and build a novel transformation to connect a problem in the time domain with a corresponding problem in the space domain while maintaining the same network lifetime. Based on this transformation, we mathematically formulate the problem and build a column-generation based algorithm, which decomposes the original formulation into two sub-formulations and iteratively solves them in a way that approaches the optimal solution. We prove that the network lifetime that can be guaranteed by the proposed algorithm is at least (1-¿) of the optimum, where ¿ can be made arbitrarily small depending on the required precision.

Future 4G cellular networks are featured with high data rate and improved coverage, which will enable realtime video multicast and broadcast services. Scalable video coding is very appropriate for wireless multicast service because it allows to choose different modulation and coding schemes (MCSs) for different video layers and can provide good video quality to users in good channel conditions while still maintaining reasonable video quality for other users. In order to apply scalable video coding to wireless multicast streaming, it is important to choose appropriate MCS for each video layer and to determine the right resource allocation among multiple video sessions. In this paper we propose a two-step dynamic programming algorithm that finds the optimal total system utility of all users where the system utility can be a generic non-negative, non-decreasing function of received rate. Our algorithm supports variable layer size and thus allows flexibility during the video encoding process. Simulation results show that our algorithm offers significant improvement on the video quality over a naive algorithm and an adapted greedy algorithm, especially in the scenarios with multiple real video sequences and limited radio resources.

In this work, we study a link-weighted and distance-constrained channel assignment problem in multi-channel mesh networks with stationary router nodes, such as community wireless networks. A good channel assignment is given as the one which can minimize interference of each link from its neighboring links and subsequently improve the network throughput. In response to it, we introduce an interference metric, namely, min-max i-value of an edge (MMIE), to explicitly accounts for interference among links that are at distance one. In addition, we further show that the link-weighted and distance-constrained channel assignment problem with respect to the interference metric is NP-hard in computation. This guides us to propose a new heuristic channel assignment algorithm called LD-CA algorithm. We study the performance of our algorithm by implementing it in a wireless simulation environment consisting of 25 nodes, each equipped with one 802.11 wireless card. The ns-2 simulation results show that in a multi-channel environment, the LD-CA algorithm significantly outperforms previously proposed channel assignment schemes by minimizing MMIE of all links.

Target coverage problem in wireless sensor networks remains a challenge. Due to nonlinear nature, previous work has mainly focused on heuristic algorithms, which remain difficult to characterize and have no performance guarantee. To solve the problem, this paper offers two important contributions. The first contribution is to have two lifetime upper bounds, which could be used to justify performance of previously proposed heuristic algorithms. One upper bound is based on the relaxation and reformulation technique while the other is derived by relaxing coverage constraints. We study the interesting connection between those two bounds and thus endow them with physical meanings. The second contribution is proposing a column generation based (CG) approach. The objective is to find an optimal schedule, defined as a time table specifying from what time up to what time which sensor watches which targets while the maximum lifetime has been obtained. We also offer an in-depth theoretic analysis as well as several novel techniques to further optimize the approach. Numerical results not only demonstrate that the lifetime upper bounds are very tight, but also verify that the proposed CG based approach constantly yields the optimal or near optimal solution.

Abstract Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical targets, which usually have different quality of service (QoS) constraints, i.e., different targets may need different sensing quality in terms of the number of transducers, sampling rate, etc. In this paper, we address the problem of optimizing network lifetime while capturing those diversified QoS coverage constraints in such surveillance sensor networks. We show that this problem belongs to NP‐complete class. We define a subset of sensors meeting QoS requirements as acoverage pattern, and if the full set of coverage patterns is given, we can mathematically formulate the problem. Directly solving this formulation however is difficult since number of coverage patterns may be exponential to number of sensors and targets. Hence, a column generation (CG)‐based approach is proposed to decompose the original formulation into two subproblems and solve them iteratively. Here a column corresponds to a feasible coverage pattern, and the idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. An initial feasible set of patterns is generated through a novel random selection algorithm (RSA), in order to launch our approach. Experimental data demonstrate that the proposed CG‐based approach is an efficient solution, even in a harsh environment. Simulation results also reveal the impact of different network parameters on network lifetime, giving certain guidance on designing and maintaining such surveillance sensor networks. Copyright © 2009 John Wiley & Sons, Ltd.

A series of environmental disasters have aroused peoplepsilas attention to the issue of diffusing-event monitoring through sensor networks. In this paper, a geography-aware fume-diffusion-spotting sensor network is investigated based on the hull theory, giving inspiration for a suite of similar diffusion-monitoring applications. In our approach, the energy consumption and the event coverage rate are tested, with the results showing notable advantage compared to the conventional random method. The experiments also indicate that the density of the network has little influence on the performance of our approach, inferring that our approach can be extended to meet the needs of network deployment in various real-world conditions.

This paper proposes an energy-efficient and collision-free medium access control protocol TDMA-WSN for wireless sensor networks. The protocol is based on time division multiple access (TDMA) principle and reduces energy consumption by avoiding overhearing, collision and idle listening. Nodes in TDMA-WSN build schedules based on information about their neighborhood to determine when they can transmit to their neighbors and when they should listen to the channel or sleep. TDMA-WSN proposes a novel resolution with three-d-hop neighborhood information to avoid collision caused by the two-hop collision-free principle used in some protocols. TDMA-WSN can accelerate passing message by arranging schedule based on routing information from the upper-layer. The simulation results indicate that TDMA-WSN outperforms contention-based protocols (e.g., S-MAC) and scheduling-based protocols (e.g., NAMA) with significant energy savings.

timization under storage constraint for wireless sensor networks with a mobile sink node. The problem is particularly challenging since we need to consider both mobility scheme and storage con- straint. Previous works suggest to use a simple single-hop routing model in which source nodes can only communication with the sink node directly in those mobile networks, However, we notice that this statement is unsuitable for sensor networks with storage constraint because we prove it is a NP-complete problem under single-hop routing model by reducing the Traveling Salesman Problem (TSP) to it in polynomial time. Hence, we try a different way. First we analyze this problem and give a lifetime upperbound, so whether this upperbound is tight is what we concern mostly. Thus, we first construct a 2-approximation O(n2) algorithm to solve the TSP problem, then a novel data diffusion mechanism is built to achieve this upperbound. We prove that under some reasonable assumptions, our algorithm can output this optimal lifetime.

optimization under coverage and connectivity requirements for sensor networks where different targets need to be monitored by different types of sensors running at possibly different sampling rates as well as different initial energy reserve. The problem is particularly challenging since we need to consider both connectiv- ity requirement and so-called target Q-coverage requirement, i.e., different targets may require different sensing quality in terms of the number of transducers, sampling rate, etc. First we formulate this NP-complete lifetime optimization problem, which is general and allows unprecedented diversity in coverage requirements, communication ranges, and sensing ranges. Our approach is based on column generation, where a column corresponds to a feasible solution; our idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. To speed up the convergence rate, we generate an initial solution through a novel random selection algorithm. Through extensive simulations, we systematically study the effect of target priorities, communication ranges, and sensing ranges on the lifetime.

Routing in intermittently connected networks(ICN) is a challenging problem due to the time varying nature of network connectivity. In this work, we focus on a special class of ICN formed by mobile ad-hoc participates called ICMAN. Asynchronous contacts become the basic way of communication in ICMANs instead of data links in traditional ad-hoc networks. Current approaches are primarily based on estimation with pure probability calculation. Stochastic forwarding decisions from statistic results can lead to disastrous routing performance when wrong choices are made. This paper introduces a new routing protocol, based on contact profile, to address the problem. To exploit the knowledge about contact profiles, we propose a contact modeling method and the corresponding contact prediction algorithm makes use of both statistic and time sequence information of contacts and allows to choose the relay that has the earliest contact to destination, which results in low average latency. Simulation is used to compare the routing performance of our algorithm with three other categories of forwarding algorithms proposed already. The results demonstrate that our scheme is more efficient in both data delivery and energy consumption than previously proposed schemes.

Many applications in wireless sensor networks like video surveillance have the requirement of timely data delivery. Real-time routing is needed in these applications. Because of the limitation of node energy, energy efficiency is also an important concern in routing protocol design in order to increase the network lifetime. In this paper, we propose a global-energy-balancing routing scheme (GEBR) for real-time traffic based on directed diffusion (DD), which balances node energy utilization to increase the network lifetime. GEBR can find an optimal path in sensor networks for data transfer considering global energy balance and limited delivery delay. Simulation results show that GEBR significantly outperforms DD in uniform energy utilization. GEBR achieves better global energy balance and longer network lifetime. The time for real-time service of the sensor networks using GEBR is prolonged by about 4.37% and the network lifetime is prolonged by 44.6%.

With the growing prevalence of wireless sensor networks comes a new need for location-based access control mechanisms. Thus we need a method to perform location verification to enforce location-based access to information resources. In this work, a statistic location verification algorithm in randomly deployed sensor networks is proposed. The nodes in the networks are classified to three roles. The claimer broadcasts the position message. The witnesses rebroadcast it and report the distance and lowest hop information to the verifier. The verifier makes use of hypothesis tests to make a decision. At last the simulation results confirm the validation of the algorithm.

Catalogue service is crucial to the sharing and utilizing of geographic information. This paper provides a new architecture and its implementation of a geographic information catalogue service that can effectively manage distributed geographic data and services. The catalogue service is based on the Open Geospatial Consortium (OGC) Catalogue Service for Web Specification and the ebXML Registry Information Model (ebRIM). The ebRIM is extended with ISO 19115 (including draft part 2) and ISO 19119 international standards for better description of geographic information. The adoption of the ebRIM and international standards will greatly advance the interoperability of the catalogue service and the sharing of the abundant geographic information. The catalogue service is Gridenabled to facilitate Grid’s abilities of on-demand, ubiquitous access to distributed computing, data, and services resources. The Grid-enabled catalogue service is GSI-supported which enables it to interoperate with other Grid Services in a secure way. By being integrated with RLS, MDS and other Gridenabled OGC Services, this Grid-enabled catalogue service prototype provides secure discovery, retrieval, and management of geographic data and services.