Connected-dominating-set (CDS) is a representative technique for constructing virtual backbones of wireless networks and thus facilitates implementation of many tasks including broadcasting, routing, etc. Most of existing works on CDS aim at constructing the minimum CDS (MCDS), so as to reduce the communication overhead over the CDS. However, MCDS may not work well in cognitive radio networks (CRNs) where communication links are prone to failure due to stochastic activities of primary users (PUs). A MCDS without consideration of the stochastic activities of PUs easily becomes invalid when the PUs become active. This study addresses a new CDS construction problem by considering the PUs’ activities. Our problem is to maximize the lifetime of the CDS while minimizing the size of the CDS, where the lifetime of a CDS is defined as the expected duration that the CDS is maintained valid. We show that the problem is NP-hard and propose a three-phase centralized algorithm. Given a CRN, the centralized algorithm can compute a CDS such that the lifetime of the CDS is maximized (optimal), and the size of the CDS is upper-bounded. We further present a two-phase localized algorithm which requires 2-hop information. Extensive simulations are conducted to evaluate the proposed algorithms.

In large-scale Internet applications running on geographically distributed datacenters, such as video streaming, it is important to efficiently allocate requests among datacenters. To the best of our knowledge, existing approaches, however, either solely focus on minimizing total cost for provider, or guaranteeing QoS for end-users. In this paper, we apply the software defined network (SDN) controller to enable the central control of the entire network, and propose a joint optimization model to consider high bandwidth utilization for provider and low delay for users. We present the Nash bargaining solution (NBS) based method to model both requirements of provider's high bandwidth utilization and end-users' low delay. Specifically, we formulate the design of request allocation under those requirements as an optimization problem, which is NP-hard. To solve such hard optimization problem, we develop an efficient algorithm blending the advantages of Logarithmic Smoothing technique and the auxiliary variable method. According to the theoretical analysis, we verify the existence and uniqueness of our solution and the convergence of our algorithm. We conduct a large amount of experiments based on real-world workload traces and demonstrate the efficiency of our algorithm compared to both greedy and locality algorithms.

Summary Fog computing is a paradigm that extends Cloud computing and services to the edge of the network. Similar to Cloud, Fog provides data, compute, storage and application services to end users. In this article, we elaborate the motivation and advantages of Fog computing and analyse its applications in a series of real scenarios, such as Smart Grid, smart traffic lights in vehicular networks and software defined networks. We discuss the state of the art of Fog computing and similar work under the same umbrella. Distinguished from other reviewing work of Fog computing, this paper further discloses the security and privacy issues according to current Fog computing paradigm. As an example, we study a typical attack, man‐in‐the‐middle attack, for the discussion of system security in Fog computing. We investigate the stealthy features of this attack by examining its CPU and memory consumption on Fog device. In addition, we discuss the authentication and authorization techniques that can be used in Fog computing. An example of authentication techniques is introduced to address the security scenario where the connection between Fog and Cloud is fragile. Copyright © 2015 John Wiley & Sons, Ltd.

The purpose of this special issue is to collate a selection of representative research articles that were primarily presented at the 12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom 2013). This annual conference brings together researchers and practitioners in the world from both academia and industry who are working on trusted computing and communications in computer systems and networks, in order to promote an exchange of ideas, discuss future collaborations, and develop new research directions.

Data traffic in cellular networks has dramatically increased in recent years as the emergence of various new wireless applications, which imposes an immediate requirement for large network capacity. Although many efforts have been made to enhance wireless channel capacity, they are far from solving the network capacity enhancement problem. Device-to-Device (D2D) communication is recently proposed as a promising technique to increase network capacity. However, most existing work on D2D communications focuses on optimizing throughput or energy efficiency, without considering economic issues. In this paper, we propose a truthful double auction for D2D communications (TAD) in multi-cell cellular networks for trading resources in frequency-time domain, where cellular users with D2D communication capability act as sellers, and other users waiting to access the network act as buyers. Both intra-cell and inter-cell D2D sellers are accommodated in TAD while the competitive space in each cell is extensively exploited to achieve a high auction efficiency. With a sophisticated seller-buyer matching, winner determination and pricing, TAD guarantees individual rationality, budget balance, and truthfulness. Furthermore, we extend our TAD design to handle a more general case that each seller and buyer ask/bid multiple resource units. Extensive simulation results show that TAD can achieve truthfulness as well as high performance in terms of seller/buyer sanctification ratio, auctioneer profit and network throughput.

Many algorithms have been introduced to deterministically authenticate Radio Frequency Identification (RFID) tags, while little work has been done to address scalability issue in batch authentications. Deterministic approaches verify tags one by one, and the communication overhead and time cost grow linearly with increasing size of tags. We design a fast and scalable counterfeits estimation scheme, INformative Counting (INC), which achieves sublinear authentication time and communication cost in batch verifications. The key novelty of INC builds on an FM-Sketch variant authentication synopsis that can capture key counting information using only sublinear space. With the help of this well-designed data structure, INC is able to provide authentication results with accurate estimates of the number of counterfeiting tags and genuine tags, while previous batch authentication methods merely provide 0/1 results indicating the existence of counterfeits. We conduct detailed theoretical analysis and extensive experiments to examine this design and the results show that INC significantly outperforms previous work in terms of effectiveness and efficiency.

This paper presents the first study on scheduling for cooperative data dissemination in a hybrid infrastructure-to-vehicle (I2V) and vehicle-to-vehicle (V2V) communication environment. We formulate the novel problem of cooperative data scheduling (CDS). Each vehicle informs the road-side unit (RSU) the list of its current neighboring vehicles and the identifiers of the retrieved and newly requested data. The RSU then selects sender and receiver vehicles and corresponding data for V2V communication, while it simultaneously broadcasts a data item to vehicles that are instructed to tune into the I2V channel. The goal is to maximize the number of vehicles that retrieve their requested data. We prove that CDS is NP-hard by constructing a polynomial-time reduction from the Maximum Weighted Independent Set (MWIS) problem. Scheduling decisions are made by transforming CDS to MWIS and using a greedy method to approximately solve MWIS. We build a simulation model based on realistic traffic and communication characteristics and demonstrate the superiority and scalability of the proposed solution. The proposed model and solution, which are based on the centralized scheduler at the RSU, represent the first known vehicular ad hoc network (VANET) implementation of software defined network (SDN) concept.

With the rising demands on cloud services, the electricity consumption has been increasing drastically as the main operational expenditure (OPEX) to data center providers. The geographical heterogeneity of electricity prices motivates us to study the task placement problem over geo-distributed data centers. We exploit the dynamic frequency scaling technique and formulate an optimization problem that minimizes OPEX while guaranteeing the quality-of-service, i.e, the expected response time of tasks. Furthermore, an optimal solution is discovered for this formulated problem. The experimental results show that our proposal achieves much higher cost-efficiency than the traditional resizing scheme, i.e, by activating/deactivating certain servers in data centers.

Software-Defined Network (SDN) is a promising network paradigm that separates the control plane and data plane in the network. It has shown great advantages in simplifying network management such that new functions can be easily supported without physical access to the network switches. However, Ternary Content Addressable Memory (TCAM), as a critical hardware storing rules for high-speed packet processing in SDN-enabled devices, can be supplied to each device with very limited quantity because it is expensive and energy-consuming. To efficiently use TCAM resources, we propose a rule multiplexing scheme, in which the same set of rules deployed on each node apply to the whole flow of a session going through but towards different paths. Based on this scheme, we study the rule placement problem with the objective of minimizing rule space occupation for multiple unicast sessions under QoS constraints. We formulate the optimization problem jointly considering routing engineering and rule placement under both existing and our rule multiplexing schemes. Via an extensive review of the state-of-the-art work, to the best of our knowledge, we are the first to study the non-routing-rule placement problem. Finally, extensive simulations are conducted to show that our proposals significantly outperform existing solutions.

Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch). In a distributed setting, each event is discovered by a sensor and reported to a robot. Here, we present novel algorithms aimed at overcoming the shortcomings of several existing solutions. We propose pairwise distance based matching algorithm (PDM) to eliminate long edges by pairwise exchanges between matching pairs. Our sequence dispatch algorithm (SQD) iteratively finds the closest event-robot pair, includes the event in dispatch schedule of the selected robot and updates its position accordingly. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. We also present generalizations which handle multiple visits and timing constraints. Our localized algorithm MAD is based on information mesh infrastructure and local auctions within the robot network for obtaining the optimal dispatch schedule for each robot. The simulations conducted confirm the advantages of our algorithms over other existing solutions in terms of average robot-event distance and lifetime.

The ever-growing cellular traffic demand has laid a heavy burden on cellular networks. The recent rapid development in vehicle-to-vehicle communication techniques makes vehicular delay-tolerant network (VDTN) an attractive candidate for traffic offloading from cellular networks. In this paper, we study a bulk traffic offloading problem with the goal of minimizing the cellular communication cost under the constraint that all the subscribers receive their desired whole content before it expires. It needs to determine the initial offloading points and the dissemination scheme for offloaded traffic in a VDTN. By novelly describing the content delivery process via a contact-based flow model, we formulate the problem in a linear programming (LP) form, based on which an online offloading scheme is proposed to deal with the network dynamics (e.g., vehicle arrival/departure). Furthermore, an offline LP-based analysis is derived to obtain the optimal solution. The high efficiency of our online algorithm is extensively validated by simulation results.

Botnets have become major engines for malicious activities in cyberspace nowadays. To sustain their botnets and disguise their malicious actions, botnet owners are mimicking legitimate cyber behavior to fly under the radar. This poses a critical challenge in anomaly detection. In this paper, we use web browsing on popular web sites as an example to tackle this problem. First of all, we establish a semi-Markov model for browsing behavior. Based on this model, we find that it is impossible to detect mimicking attacks based on statistics if the number of active bots of the attacking botnet is sufficiently large (no less than the number of active legitimate users). However, we also find it is hard for botnet owners to satisfy the condition to carry out a mimicking attack most of the time. With this new finding, we conclude that mimicking attacks can be discriminated from genuine flash crowds using second order statistical metrics. We define a new fine correntropy metrics and show its effectiveness compared to others. Our real world data set experiments and simulations confirm our theoretical claims. Furthermore, the findings can be widely applied to similar situations in other research fields.

Vehicular Cyber-Physical System (VCPS) provides CPS services via exploring the sensing, computing and communication capabilities on vehicles. VCPS is deeply influenced by the performance of the underlying vehicular network with intermittent connections, which make existing routing solutions hardly to be applied directly. Epidemic routing, especially the one using random linear network coding, has been studied and proved as an efficient way in the consideration of delivery performance. Much pioneering work has tried to figure out how epidemic routing using network coding (ERNC) performs in VCPS, either by simulation or by analysis. However, none of them has been able to expose the potential of ERNC accurately. In this paper, we present a stochastic analytical framework to study the performance of ERNC in VCPS with intermittent connections. By novelly modeling ERNC in VCPS using a token-bucket model, our framework can provide a much more accurate results than any existing work on the unicast delivery performance analysis of ERNC in VCPS. The correctness of our analytical results has also been confirmed by our extensive simulations.

Unknown RFID tags appear when the unread tagged objects are moved in or tagged objects are misplaced. This paper studies the practically important problem of unknown tag detection while taking both time-efficiency and energy-efficiency of battery-powered active tags into consideration. We first propose a Sampling Bloom Filter which generalizes the standard Bloom Filter. Using the new filtering technique, we propose the Sampling Bloom Filter-based Unknown tag Detection Protocol (SBF-UDP), whose detection accuracy is tunable by the end users. We present the theoretical analysis to minimize the time and energy costs. SBF-UDP can be tuned to either the time-saving mode or the energy-saving mode, according to the specific requirements. Extensive simulations are conducted to evaluate the performance of the proposed protocol. The experimental results show that SBF-UDP considerably outperforms the previous related protocols in terms of both time-efficiency and energy-efficiency. For example, when 3 or more unknown tags appear in the RFID system with 30000 known tags, the proposed SBF-UDP is able to successfully report the existence of unknown tags with a confidence more than 99%. While our protocol runs 9 times faster than the fastest existing scheme and reducing the energy consumption by more than 80%.

Malware is pervasive in networks, and poses a critical threat to network security. However, we have very limited understanding of malware behavior in networks to date. In this paper, we investigate how malware propagates in networks from a global perspective. We formulate the problem, and establish a rigorous two layer epidemic model for malware propagation from network to network. Based on the proposed model, our analysis indicates that the distribution of a given malware follows exponential distribution, power law distribution with a short exponential tail, and power law distribution at its early, late and final stages, respectively. Extensive experiments have been performed through two real-world global scale malware data sets, and the results confirm our theoretical findings.

In cyber physical system (CPS), computational resources and physical resources are strongly correlated and mutually dependent. Cascading failures occur between coupled networks, cause the system more fragile than single network. Besides widely used metric giant component, we study small cluster (small component) in interdependent networks after cascading failures occur. We first introduce an overview on how small clusters distribute in various single networks. Then we propose a percolation theory based mathematical method to study how small clusters be affected by the interdependence between two coupled networks. We prove that the upper bounds exist for both the fraction and the number of operating small clusters. Without loss of generality, we apply both synthetic network and real network data in simulation to study small clusters under different interdependence models and network topologies. The extensive simulations highlight our findings: except the giant component, considerable proportion of small clusters exists, with the remaining part fragmenting to very tiny pieces or even massive isolated single vertex; no matter how the two networks are tightly coupled, an upper bound exists for the size of small clusters. We also discover that the interdependent small-world networks generally have the highest fractions of operating small clusters. Three attack strategies are compared: Inter Degree Priority Attack, Intra Degree Priority Attack and Random Attack. We observe that the fraction of functioning small clusters keeps stable and is independent from the attack strategies.

In this paper, we study two tightly coupled issues, space-crossing community detection and its influence on data forwarding in mobile social networks (MSNs). We propose a communication framework containing the hybrid underlying network with access point (AP) support for data forwarding and the base stations for managing most of control traffic. The concept of physical proximity community can be extended to be one across the geographical space, because APs can facilitate the communication among long-distance nodes. Space-crossing communities are obtained by merging some pairs of physical proximity communities. Based on the space-crossing community, we define two cases of node local activity and use them as the input of inner product similarity measurement. We design a novel data forwarding algorithm Social Attraction and Infrastructure Support (SAIS), which applies similarity attraction to route to neighbor more similar to destination, and infrastructure support phase to route the message to other APs within common connected components. We evaluate our SAIS algorithm on real-life datasets from MIT Reality Mining and University of Illinois Movement (UIM). Results show that space-crossing community plays a positive role in data forwarding in MSNs. Based on this new type of community, SAIS achieves a better performance than existing popular social community-based data forwarding algorithms in practice, including Simbet, Bubble Rap and Nguyen's Routing algorithms.

Abstract—Fog Computing is a paradigm that extends Cloud computing and services to the edge of the network. Similar to Cloud, Fog provides data, compute, storage, and application services to end-users. In this article, we elaborate the motivation and advantages of Fog computing, and analyse its applications in a series of real scenarios, such as Smart Grid, smart traffic lights in vehicular networks and software defined networks. We discuss the state-of-the-art of Fog computing and similar work under the same umbrella. Security and privacy issues are further disclosed according to current Fog computing paradigm. As an example, we study a typical attack, man-in-the-middle attack, for the discussion of security in Fog computing. We investigate the stealthy features of this attack by examining its CPU and memory consumption on Fog device.

In this paper, we study two tightly coupled issues: space-crossing community detection and its influence on data forwarding in Mobile Social Networks (MSNs) by taking the hybrid underlying networks with infrastructure support into consideration. The hybrid underlying network is composed of large numbers of mobile users and a small portion of Access Points (APs). Because APs can facilitate the communication among long-distance nodes, the concept of physical proximity community can be extended to be one across the geographical space. In this work, we first investigate a space-crossing community detection method for MSNs. Based on the detection results, we design a novel data forwarding algorithm SAAS (Social Attraction and AP Spreading), and show how to exploit the space-crossing communities to improve the data forwarding efficiency. We evaluate our SAAS algorithm on real-life data from MIT Reality Mining and University of Illinois Movement (UIM). Results show that space-crossing community plays a positive role in data forwarding in MSNs in terms of delivery ratio and delay. Based on this new type of community, SAAS achieves a better performance than existing social community-based data forwarding algorithms in practice, including Bubble Rap and Nguyen's Routing algorithms.

Among the current clustering algorithms of complex networks, Laplacian-based spectral clustering algorithms have the advantage of rigorous mathematical basis and high accuracy. However, their applications are limited due to their dependence on prior knowledge, such as the number of clusters. For most of application scenarios, it is hard to obtain the number of clusters beforehand. To address this problem, we propose a novel clustering algorithm - Jordan-Form of Laplacian-Matrix based Clustering algorithm (JLMC). In JLMC, we propose a model to calculate the number (n) of clusters in a complex network based on the Jordan-Form of its corresponding Laplacian matrix. JLMC clusters the network into n clusters by using our proposed modularity density function (P function). We conduct extensive experiments over real and synthetic data, and the experimental results reveal that JLMC can accurately obtain the number of clusters in a complex network, and outperforms Fast-Newman algorithm and Girvan-Newman algorithm in terms of clustering accuracy and time complexity.

We consider the problem of broadcasting a message in a mobile ad hoc network (MANET) with the objective of minimizing the broadcast latency. Due to the mobility of network nodes, the coordination among nodes is hard and expensive. Thus it is much desired to design efficient, one-sided broadcast protocols where each node acts according to its own state solely. Although random scheduling is a popular and effective one-sided approach for leveraging the broadcast nature of wireless medium while coping with transmission collisions, both critical for reducing the broadcast latency, in this paper, we show that when nodes move very fast, the performance of pure random scheduling must be sub-optimal, no matter how the forwarding probabilities are specified. Furthermore, we propose a novel one-sided broadcast protocol named R2, which first splits the message into a certain number of mini-messages and then couples a fine-grained random scheduling with random linear network coding for broadcasting the mini-messages. Theoretical analyses demonstrate that R$^2$ performs optimally in order sense, no matter how fast network nodes move around, although different mobility has distinct effect on the speed of message broadcast.

Machine-to-Machine (M2M) paradigm enables machines (sensors, actuators, robots, and smart meter readers) to communicate with each other with little or no human intervention. M2M is a key enabling technology for the cyber-physical systems (CPSs). This paper explores CPS beyond M2M concept and looks at futuristic applications. Our vision is CPS with distributed actuation and in-network processing. We describe few particular use cases that motivate the development of the M2M communication primitives tailored to large-scale CPS. M2M communications in literature were considered in limited extent so far. The existing work is based on small-scale M2M models and centralized solutions. Different sources discuss different primitives. Few existing decentralized solutions do not scale well. There is a need to design M2M communication primitives that will scale to thousands and trillions of M2M devices, without sacrificing solution quality. The main paradigm shift is to design localized algorithms, where CPS nodes make decisions based on local knowledge. Localized coordination and communication in networked robotics, for matching events and robots, were studied to illustrate new directions.

Smart micro-grids can produce “renewable” energy and store them in power storage devices. Power loss, however, is a significant problem in power exchange among the micro-grids and between the macro-station and individual micro-grids. To optimally reduce the total power losses in such a power grid system, in this paper, a greedy coalition formation algorithm is proposed, which allows the macro-station to coordinate mutual power exchange among the micro-grids and between each micro-grid and the macro-station. Our algorithm optimizes the total power losses across the entire power grid, including the cost of charging and discharging power storage devices and power losses due to power transfers. The algorithm creates exchange pairs among the micro-grids, giving priority to pairs with higher power loss reduction per exchanged power unit. Through computer-based simulations, we demonstrate that the proposed approach significantly reduces the average power loss compared with the conventional noncooperative method. The simulations also demonstrate that the communications overhead of our proposal (due to negotiations aimed at forming coalitions) does not significantly affect the available communication resource.

For multiple heterogeneous multicore server processors across clouds and data centers, the aggregated performance of the cloud of clouds can be optimized by load distribution and balancing. Energy efficiency is one of the most important issues for large-scale server systems in current and future data centers. The multicore processor technology provides new levels of performance and energy efficiency. The present paper aims to develop power and performance constrained load distribution methods for cloud computing in current and future large-scale data centers. In particular, we address the problem of optimal power allocation and load distribution for multiple heterogeneous multicore server processors across clouds and data centers. Our strategy is to formulate optimal power allocation and load distribution for multiple servers in a cloud of clouds as optimization problems, i.e., power constrained performance optimization and performance constrained power optimization. Our research problems in large-scale data centers are well-defined multivariable optimization problems, which explore the power-performance tradeoff by fixing one factor and minimizing the other, from the perspective of optimal load distribution. It is clear that such power and performance optimization is important for a cloud computing provider to efficiently utilize all the available resources. We model a multicore server processor as a queuing system with multiple servers. Our optimization problems are solved for two different models of core speed, where one model assumes that a core runs at zero speed when it is idle, and the other model assumes that a core runs at a constant speed. Our results in this paper provide new theoretical insights into power management and performance optimization in data centers.

At present, companies and standards organizations are enhancing Ethernet as the unified switch fabric for all of the TCP/IP traffic, the storage traffic and the high performance computing traffic in data centers. Backward congestion notification (BCN) is the basic mechanism for the end-to-end congestion management enhancement of Ethernet. To fulfill the special requirements of the unified switch fabric, i.e., losslessness and low transmission delay, BCN should hold the buffer occupancy around a target point tightly. Thus, the stability of the control loop and the buffer size are critical to BCN. Currently, the impacts of delay on the performance of BCN are unidentified. When the speed of Ethernet increases to 40 Gbps or 100 Gbps in the near future, the number of on-the-fly packets becomes the same order with the buffer size of switch. Accordingly, the impacts of delay will become significant. In this paper, we analyze BCN, paying special attention on the delay. We model the BCN system with a set of segmented delayed differential equations, and then deduce sufficient condition for the uniformly asymptotic stability of BCN. Subsequently, the bounds of buffer occupancy are estimated, which provides direct guidelines on setting buffer size. Finally, numerical analysis and experiments on the NetFPGA platform verify our theoretical analysis.

Existing solutions to carrier-based sensor placement by a single robot in a bounded unknown Region of Interest (ROI) do not guarantee full area coverage or termination. We propose a novel localized algorithm, named Back-Tracking Deployment (BTD). To construct a full coverage solution over the ROI, mobile robots (carriers) carry static sensors as payloads and drop them at the visited empty vertices of a virtual square, triangular, or hexagonal grid. A single robot will move in a predefined order of directional preference until a dead end is reached. Then it back-tracks to the nearest sensor adjacent to an empty vertex (an “entrance” to an unexplored/uncovered area) and resumes regular forward movement and sensor dropping from there. To save movement steps, the back-tracking is carried out along a locally identified shortcut. We extend the algorithm to support multiple robots that move independently and asynchronously. Once a robot reaches a dead end, it will back-track, giving preference to its own path. Otherwise, it will take over the back-track path of another robot by consulting with neighboring sensors. We prove that BTD terminates within finite time and produces full coverage when no (sensor or robot) failures occur. We also describe an approach to tolerate failures and an approach to balance workload among robots. We then evaluate BTD in comparison with the only competing algorithms SLD [Chang et al. 2009a] and LRV [Batalin and Sukhatme 2004] through simulation. In a specific failure-free scenario, SLD covers only 40--50% of the ROI, whereas BTD covers it in full. BTD involves significantly (80%) less robot moves and messages than LRV.

Nowadays, networks play an indispensable role in social life, and social networks have become a new advertising medium for offline activities. Previous studies of information diffusion or behavior spread over social networks have mostly focused on diffusion models and analysis of virtual interaction between online users, and very few of them focus on the propagation of real world activities in these social networks. To address this problem, we use data obtained from the Chinese largest recommendation social network - Douban, and study how the offline activities spread from one user to another through Douban. By using cascading subgraphs and diffusion trees, we break a whole cascade into local subgraphs. After analyzing the activities of about 1.47 million users, we observe the statistical and topological characteristics of these local cascading subgraphs. Next, we find the size and degree distributions of these cascading subgraphs and several common patterns of topology of local cascades. Moreover, we also have some other interesting discoveries, like the relation between the number of initial adopters and the final cascade size, and the underlying influences driving user behaviors. Finally, we propose a diffusion model that can generate information cascades that follow the patterns we have observed, and validate it by empirical analysis.

Given a set of events and a set of robots, the dispatch problem is to allocate one robot for each event to visit it. In a single round, each robot may be allowed to visit only one event (matching dispatch), or several events in a sequence (sequence dispatch problem). The distributed version of the problem is embedded into a sensor network field, where each event is discovered by a sensor and reported to a robot. Existing centralized and distributed solution based on stable marriage problem suffers from the presence of long robot paths. The other existing solution, based on k-means clustering and traveling salesman tour, suffers from the design goal of allocating the same number of events to each robot. We propose pair wise distance based matching (PDM) algorithm, to eliminate long matching edges by pair wise exchanges among two robot-event pairs to reduce overall path length. Our sequence dispatch (SQD) algorithm finds the closest robot for each free event, and, iteratively, selects closest event-robot pair while moving selected robot to the new position and updating other distances to reflect that new position. When event-robot distances are multiplied by robot resistance (inverse of the remaining energy), the corresponding energy-balanced variants are obtained. Our localized algorithm (MAD) is based on information mesh infrastructure for finding nearby robot, and local auctions in robot network to perhaps find a better one.

In order to optimize energy consumption in smart grid, demand side management has gained a lot of attention recently. While existing research works attempt to optimize energy consumption either from the view point of the power company or that of users, we investigate whether it is possible to consider both parties' interests at the same time. In this paper, we propose a novel energy price model, which is a function of the total energy consumption in the considered system. In addition, a new objective function, to optimize the difference between the value and cost of energy, is proposed. The power company sends the energy price parameter and the latest consumption summary vector information to the users sequentially. Upon receiving these information, a user can optimize his own schedule and report it to the company. The company then updates its energy price parameter before communicating with the next customers. A two-step centralized game is proposed that models this interaction between the power company and its consumers. The game aims at reducing the system peak-to-average power ratio by simultaneously optimizing users' energy schedules and lowering the overall energy consumption in the system. Through simulation results the performance of the proposed game-based demand side management technique is evaluated.

We propose a novel architecture of data center networks (DCN), which adds wireless network card to both servers and routers. Existing traffic redundancy elimination (TRE) mechanisms reduce link loads and increase network capacity in several environments by removing strings that have appeared in earlier packets through encoding and decoding them several hops downstream. This article is the first to explore TRE mechanisms in large-scale DCNs and the first to exploit cooperative TRE among servers. Moreover, it also achieves the `logically centralized' control over the physically distributed states in emerging software defined networks (SDN) paradigm, by sharing information among servers and routers in data centers with wireless cards. We first formulate the TREDaCeN (TRE in Data Center Networks) problem and reduce the cycle cover problem to prove that finding an optimal caching task assignment for TREDaCeN problem is NP-hard. We further describe an offline TREDaCeN algorithm which is proved to have good approximation ratio. We then discuss efficient online zero-delay and semi-distributed implementations of TREDaCeN supported by physical proximity of servers and routers, enabling status updates in a single wireless transmission, using an efficient prioritized schedule. We also address online cache replacement and consistency of information in servers and routers with and without delay. Our framework is tested on different parameters and shows superior performance in comparison to other mechanisms (imported directly to this setting). Our results show the robustness and the trade-off between the `logically centralized' implementation and the overhead on handling inconsistency of distributed information in DCN.

Beaconless or contention-based geographic routing algorithms forward packets toward a geographical destination reactively without the knowledge of the neighborhood. Such algorithms allow greedy forwarding, where only the next hop neighbor responds after a timer-based contention using only three messages (RTS, CTS, and DATA) per forwarding step. However, existing contention-based schemes for recovery from greedy failures do not have this property. In this paper, we show that recovery is possible within this 3-message scheme: the Rotational Sweep (RS) algorithm directly identifies the next hop after timer-based contention and constructs a traversal path that ensures progress after a greedy failure. It uses a traversal scheme (called Sweep Circle) that forwards a message along the $(\alpha)$-shape of the network and provides recovery paths shorter or equal to the prominent face routing with Gabriel graph planarization. An alternative traversal scheme (called Twisting Triangle) provides even shorter routes on average, as shown by simulations. They both also reduce per-node overall network contention delays. We prove that both traversal schemes guarantee delivery in unit disk graphs. Our traversal schemes avoid planarization and are easy to implement, based merely on the evaluation of a function of a neighbor node's relative position. They can also be used for boundary detection and improve path-length in conventional beacon-based routing.

We address pairwise and (for the first time) triple key establishment problems in wireless sensor networks (WSN). Several types of combinatorial designs have already been applied in key establishment. A BIBD(v, b, r, k, λ) (or t - (v, b, r, k, λ) design) can be mapped to a sensor network, where v represents the size of the key pool, b represents the maximum number of nodes that the network can support, and k represents the size of the key chain. Any pair (or t-subset) of keys occurs together uniquely in exactly λ nodes; λ = 2 and λ = 3 are used to establish unique pairwise or triple keys. We use several known constructions of designs with λ = 2, to predistribute keys in sensors. We also describe a new construction of a design called strong Steiner trade and use it for pairwise key establishment. To the best of our knowledge, this is the first paper on application of trades to key distribution. Our scheme is highly resilient against node capture attacks (achieved by key refreshing) and is applicable for mobile sensor networks (as key distribution is independent on the connectivity graph), while preserving low storage, computation and communication requirements. We introduce a novel concept of triple key distribution, in which three nodes share common keys, and discuss its application in secure forwarding, detecting malicious nodes and key management in clustered sensor networks. We present a polynomial-based and a combinatorial approach (using trades) for triple key distribution. We also extend our construction to simultaneously provide pairwise and triple key distribution scheme, and apply it to secure data aggregation.

The IEEE Computer Society (CS) established the Reviewer Appreciation Program (RAP) at the end of 2012, to recognize Distinguished Reviewers. The key enabler for this program is the reviewer statistics, which are made available by S1M. I requested these statistics in 2010 for IEEE Transactions on Parallel and Distributed Systems (TPDS) and used them in making decisions on new TPDS editors (as one of factors) in 2011. The information fi nally became available (for all CS transactions) in a reasonable size (Excel) file during 2012, sortable by any column. Therefore, EICs are able to see a list of reviewers sorted by the number of submitted reviews for any time period. RAP intends to recognize our Distinguished Reviewers at the end of each year. Editors were asked to nominate their top quality reviewers (which have no COI with them) for reviews made in 2012. Following 6 nominations by editors, 3 winners (Gilbert Hendry, Zubair Md. Fadlullah, and Ben Leong) were selected. The Outstanding Reviewer Service Award for the TPDS All-Time Most Prolific Reviewer is awarded to Yu-Kwong (Ricky) Kwok. He appears to be our star reviewer called by many editors, and was discovered only by this program (and was immediately invited to become a TPDS editor; please see his short biography). He made, by far, the most reviews (57; 44 as Yu-Kwong plus 13 as Ricky, which came as two separate entries in the file) made for TPDS. Other winners are Jelena Misic (37 reviews), Yu Wang (33), Yingshu Li (32), Jiangchuan Liu (32), Kui Ren (31), Chuan Wu (31), Weisong Shi (28), Haiying Shen (27), Nathalie Mitton (25), Govindarasu Manimaran (24), Song Jiang (23), Hongyi Wu (23), Tian He (22), Xue Liu (22), Henri Casanova (21), Bin Xiao (21), Hannes Frey (20), Mo Li (20), Hai Liu (20), Guoliang Xing (20), Wei Yu (20), Dror Feitelson (19), Stella Kafetzoglou (19), and Qun Li (19). Three of them are new TPDS editors and featured below.

I am pleased to learn

Transactions on Parallel and Distributed Systems (TPDS

During the route discovery process, each node receiving the route request packet (RReq) will retransmit it exactly once. A distant neighbor may accidentally receive/loose the only RReq and use it to announce a new route, although that link is inferior/superior for route reply packet (RRep) or actual message routing. Overall, the constructed route may be far from the optimal. All existing route discovery schemes (including DSR/AODV) apply retransmission during route discovery exactly once (1R). Based on a realistic physical layer model, we propose two new route discovery schemes: n-retransmission (nR, retransmitting exactly n times) and n-retransmission c-reception (ncRR), retransmitting until either a total of n own retransmissions or c copies from neighbors are heard. We compare our two new scheme with traditional one, under otherwise same conditions (same metric, same packet reception probability on each link) and same choices about possibly retransmitting again upon discovering better route (R+) or discarding it (R1), generating route reply packet for every received RRep (B*), or for first and better discovered route (B2), and retransmit ting RRep exactly once (A1), maximum three times (A3), or optimally u times decided by link quality (Au). Experimental results also show that the proposed ncRR scheme (for n=2 and c=3 or c=4) achieves the best tradeoff between quality of route, success rate and message overhead in route discovery process, followed by nR scheme, and both of them are superior to the existing traditional based schemes.

Power-aware routing and controlled mobility schemes are two commonly used mechanisms for improving communications in a wireless sensor network. While the former actively consider the transmission costs when selecting the next hop on the route, the latter instruct mobile relay nodes (either sensors or actuators) to pursue more promising locations so as to optimize end-to-end transmission power. Rarely, if ever, the two methodologies are exploited together for achieving relevant energy savings and prolonging network lifetime. In this paper, we introduce a hybrid routing-mobility model for the optimization of network communications. First, we find a multi-hop path between a source and its destination in an energy-efficient fashion and then we move all hop nodes in an uninterrupted, straight manner to some predefined spots with optimal energy-saving properties, fully preserving the path connectivity as they move. Such synergetic approach allowed us to: (1) seamlessly guarantee message delivery regardless of the network density (average number of neighbors per node), (2) easily incorporate any power-related optimization criterion to the routing protocol and (3) even target scenarios where both end nodes are actually disconnected from each other. Results gathered from extensive simulations argue for the introduction of the proposed hybrid framework.

Mobile robots nowadays can assist wireless sensor networks (WSNs) in many jeopardizing scenarios that unexpectedly arise during their operational lifetime. We focus on an emerging kind of cooperative networking system in which a small team of robotic agents lies at a base station. Their mission is to service an already-deployed WSN by periodically replacing all damaged sensors in the field with passive, spare ones so as to preserve the existing network coverage. This novel application scenario is here baptized as “multiple-carrier coverage repair” (MC2R) and modeled as a new generalization of the vehicle routing problem. A hybrid metaheuristic algorithm is put forward to derive nearly-optimal sensor replacement trajectories for the robotic fleet in a short running time. The composite scheme relies on a swarm of artificial fireflies in which each individual follows the exploratory principles featured by Harmony Search. Infeasible candidate solutions are gradually driven into feasibility under the influence of a weak Pareto dominance relationship. A repair heuristic is finally applied to yield a full-blown solution. To the best of our knowledge, our scheme is the first one in literature that tackles MC2R instances. Empirical results indicate that promising solutions can be achieved in a limited time span.

We propose to apply the concept of Cost-to-Progress Ratio (CPR) in greedy routing for load reduction and balancing. The load of a node is the percentage of time it is occupied by forwarding traffic or inability to forward due to interference. The resultant routing protocol, named CPR-routing, is a localized parameterless approach, optimizing the ratio of nodal load and geographic progress. Through extensive simulation, we evaluate it in comparison with an existing parameter-based localized solution, α-routing. Our simulation results indicate that CPR-routing outperforms α-routing in per node load, success rate, and average hop count.

To improve safety, a warning message in VANETs should be delivered both reliably and urgently. Existing solutions either tend to compromise propagation delay or do not reach high reliability due to broadcast storm problem caused by excessive retransmissions. We propose ReC, which exploits geographical information to help nodes autonomously achieve agreement on forwarding strategies. Each forwarding candidate ranks itself and its neighbors (who affirmatively or potentially received the message already) by distance to the centroid of neighbors in need of message, to assign different priority in forwarding among neighboring nodes and remarkably suppress unnecessary retransmission, while enabling best nodes to transmit the packet without waiting. The effectiveness and efficiency of this method is validated through extensive simulations under 802.11p settings. The results demonstrate that the proposed protocol achieves the high reliability of leading state-of-the-art solutions, while at the same time significantly enhances timeliness, dedicating itself to disseminating emergency messages in 2D vehicular networks.

Summary form only given, as follows. Mobile devices (smart phones, tablets, laptops, embedded boards, robots) can serve as terminals for cloud computing services over intelligent network. Mobile cloud has emerged as a new cloud computing platform that 'puts cloud into a pocket.' Important issues include optimizing the scheduling and transport schemes, access management, and application optimization, for mobile devices to achieve energy saving. This talk will first introduce the development of mobile cloud computing and describe some applications involving multimedia, vision/recognition, graphics, gaming, text processing. It will present the transmission, computation (e.g. task outsourcing), and sensing (e.g. location based services) challenges and solution approaches of green computing in mobile cloud. 'Crowd computing' combines mobile devices and social interactions to achieve large-scale distributed computation. Examples include task farming and social network creation and cooperation. Mobile devices are being equipped with various sensors to provide input for participatory and opportunistic crowd-sourced sensing. Particular emerging concepts are 'vehicular cloud' and 'vehicular crowd,' with applications such as cloud server, vehicular data center, and congestion mitigation.

In a broadcasting task, source node wants to send the same message to all the other nodes in the network. Existing solutions address specific mobility scenarios, e.g. connected dominating set (CDS) based for static networks, blind flooding for moderate mobility, hyper flooding for highly mobile and frequently partitioned networks. We are interested in designing a unique protocol that will seamlessly (without using any parameter) adjust itself to any mobility scenario, and with capability to address various model assumptions and optimality criteria. Existing approaches for all scenarios are based on some threshold parameters (e.g. speed) to locally select among different algorithms, and therefore different nodes may run different algorithms. Here we describe a novel general BSM (Broadcasting from Static to Mobile) framework, built over several recent algorithms handling special cases. It aims at high delivery rate with low message cost, and addresses intermittent connectivity and delay minimization. Each node activates with respect to broadcast message whenever it identifies one or more neighbors in need of the message. It selects, upon activation, waiting time (dynamically adjusted with reception of any message) depending on the number of such neighbors, distance to their centroid, and its CDS membership. It competes (at MAC layer) to retransmit at timeout expiry if it still believes that a neighbor needs message. We map this algorithm to variety of multi-hop wireless networks scenarios, with and without: positional information, acknowledgments, and time criticality goal. Some existing solutions are derived as special cases, and we also show how to timely deliver warnings in vehicular networks with arbitrary road structure, without using road maps.

Recently, companies and standards organizations are enhancing Ethernet as the unified switch fabric for all of the TCP/IP traffic, the storage traffic and the interprocess communication(IPC) traffic in Data Center Networks(DCNs). Backward Congestion Notification(BCN) is the basic mechanism for the end-to-end congestion management enhancement. To fulfill the special requirements of the unified switch fabric that being lossless and of extremely low latency, BCN should hold the queue length around a target point tightly. Thus, the stability of the control loop and the buffer size are critical to BCN. Currently, the impacts of delay on the performance of BCN are unidentified. When the link capacity increases to 40Gbps or 100Gbps in the near future, the number of on-the-fly packets becomes the same order with the shallow buffer size of switches. Thus, the impacts of delay on the performance of BCN will become significant. In this paper, we analyze BCN, paying special attention on the delay. Firstly, we model the BCN system with a set of segmented delayed differential equations. Then, the sufficient condition for the uniformly asymptotic stability of the BCN system is deduced. Subsequently, the bound of buffer occupancy under this sufficient condition are estimated, which provides guidelines on setting buffer size. Finally, the numerical analysis and the experiments on the NetFPGA platform verify the theoretical analysis.

Botnets are the engine for malicious activities in cyber space. In order to sustain their botnets and disguise their illegal actions, botnet owners are exhausting their strength to mimic legitimate cyber behavior to fly under the radar, e.g. flash crowd mimicking attacks on popular websites. It is an open and challenging problem: can we beat mimicking attacks or not? We use web browsing on popular websites as an example to explore the issue. In our previous work, we discovered that it is almost impossible to detect mimicking attacks from statistics if the number of active bots of a botnet is sufficient (no less than the number of active legitimate users). In this paper, we pointed out that it is usually hard for botnet owners to have sufficient number of active bots in practice. Therefore, we can discriminate mimicking attacks when the sufficient number condition is not met. We prove our claim theoretically and confirm it with simulations. Our findings can also be applied to a large number of other detection related cases.

We propose a novel localized Integrated Location Service and Routing (ILSR) scheme, based on the geographic routing protocol GFG, for data communications from sensors to a mobile sink in wireless sensor networks. The objective is to enable each sensor to maintain a slow-varying routing next hop to the sink rather than the precise knowledge of quick-varying sink position. In ILSR, sink updates location to neighboring sensors after or before a link breaks and whenever a link creation is observed. Location update relies on flooding, restricted within necessary area, where sensors experience (next hop) change in GFG routing to the sink. Dedicated location update message is additionally routed to selected nodes for prevention of routing failure. Considering both unpredictable and predictable (controllable) sink mobility, we present two versions. We prove that both of them guarantee delivery in a connected network modeled as unit disk graph. ILSR is the first localized protocol that has this property. We further propose to reduce message cost, without jeopardizing this property, by dynamically controlling the level of location update. A few add-on techniques are as well suggested to enhance the algorithm performance. We compare ILSR with an existing competing algorithm through simulation. It is observed that ILSR generates routes close to shortest paths at dramatically lower (90% lower) message cost.

We propose a broadcast algorithm suitable for a wide range of vehicular scenarios, which only employs local information acquired via periodic beacon messages, containing acknowledgments of the circulated broadcast messages. Each vehicle decides whether it belongs to a connected dominating set (CDS). Vehicles in the CDS use a shorter waiting period before possible retransmission. At time-out expiration, a vehicle retransmits if it is aware of at least one neighbor in need of the message. To address intermittent connectivity and appearance of new neighbors, the evaluation timer can be restarted. Our algorithm resolves propagation at road intersections without any need to even recognize intersections. It is inherently adaptable to different mobility regimes, without the need to classify network or vehicle speeds. In a thorough simulation-based performance evaluation, our algorithm is shown to provide higher reliability and message efficiency than existing approaches for nonsafety applications.

In this paper, we propose a novel trust management scheme for improving routing reliability in wireless ad hoc networks. It is grounded on two classic autoregression models, namely Autoregressive (AR) model and Autoregressive with exogenous inputs (ARX) model. According to this scheme, a node periodically measures the packet forwarding ratio of its every neighbor as the trust observation about that neighbor. These measurements constitute a time series of data. The node has such a time series for each neighbor. By applying an autoregression model to these time series, it predicts the neighbors future packet forwarding ratios as their trust estimates, which in turn facilitate it to make intelligent routing decisions. With an AR model being applied, the node only uses its own observations for prediction; with an ARX model, it will also take into account recommendations from other neighbors. We evaluate the performance of the scheme when AR, ARX or a previously proposed Bayesian model is used. Simulation results indicate that the ARX model is the best choice in terms of accuracy.

We address pairwise and (for the first time) triple key establishment problems in wireless sensor networks (WSN). We use combinatorial designs to establish pairwise keys between nodes in a WSN. A BIBD(v; b; r; k; λ) (or t - (v; b; r; k; λ)) design can be mapped to a sensor network, where v represents the size of the key pool, b represents the maximum number of nodes that the network can support, k represents the size of the key chain. Any pair (or t-subset) of keys occurs together uniquely in exactly λ nodes. λ = 2 and λ = 3 are used to establish unique pairwise or triple keys. Our pairwise key distribution is the first one that is fully secure (none of the links among uncompromised nodes is affected) and applicable for mobile sensor networks (as key distribution is independent on the connectivity graph), while preserving low storage, computation and communication requirements. We also use combinatorial trades to establish pairwise keys. This is the first time that trades are being applied to key management. We describe a new construction of Strong Steiner Trades. We introduce a novel concept of triple key distribution, in which a common key is established between three nodes. This allows secure passive monitoring of forwarding progress in routing tasks. We present a polynomial-based approach and a combinatorial approach (using trades) for triple key distribution.

In mission-critical activities, each user is allowed to access some specific, but not all, data gathered by wireless sensor networks. Yu et al recently proposed a centralized fine grained data access control mechanism for sensor networks, which exploits a cryptographic primitive called attribute based encryption (ABE). There is only one trusted authority to distribute keys to the sensor nodes and the users. Compromising the single authority can undermine the whole network. We propose a fully distributed access control method, which has several authorities instead of one. Each sensor has a set of attributes and each user has an access structure of attributes. A message from a sensor is encrypted such that only a user with matching set of attributes can decrypt. Compared to, our schemes need simpler access structure which make secret key distribution more computation efficient, when user rights are modified. We prove that our scheme can tolerate compromising all but one distribution centers, which independently distribute their contributions to a single user key. Our scheme do not increase the computation and communication costs of the sensors, making it highly desirable for fine grained access control.

We propose a localized Delay-bounded and Energy-efficient Data Aggregation scheme (DEDA) for wireless sensor and actor networks that are modeled as undirected graphs (URG). The scheme is based on a novel concept of Desired Hop Progress (DHP) and designed for low-traffic, request-driven network scenarios, where delay is proportional to hop count [10]. It builds a local minimal spanning tree (LMST) sub-graph of the network with links weighted by transmission powers. Using edges from LMST, it constructs a shortest path (thus energy-efficient) tree rooted at actor (sink) for data aggregation. The tree is used as is if it generates acceptable delay. Otherwise, it is adjusted by replacing LMST sub-paths with URG edges. The adjustment is done locally, according to the DHP value at each node, with hop count reduction corresponding to the delay allowance per hop (ratio of current LMST delay over maximal allowed one). Through extensive simulation, we show that DEDA may save 25–75% energy per node on average and extend up to 150% network life, depending on network conditions, in comparison with the only existing competing localized solution [11].

We propose a new model for data storage and access in clouds. Our scheme avoids storing multiple encrypted copies of same data. In our framework for secure data storage, cloud stores encrypted data (without being able to decrypt them). The main novelty of our model is addition of key distribution centers (KDCs). We propose DACC (Distributed Access Control in Clouds) algorithm, where one or more KDCs distribute keys to data owners and users. KDC may provide access to particular fields in all records. Thus, a single key replaces separate keys from owners. Owners and users are assigned certain set of attributes. Owner encrypts the data with the attributes it has and stores them in the cloud. The users with matching set of attributes can retrieve the data from the cloud. We apply attribute-based encryption based on bilinear pairings on elliptic curves. The scheme is collusion secure; two users cannot together decode any data that none of them has individual right to access. DACC also supports revocation of users, without redistributing keys to all the users of cloud services. We show that our approach results in lower communication, computation and storage overheads, compared to existing models and schemes.

Access control ensures that only authorized users have access to data and services. This problem becomes challenging in distributed systems, where coordination of activities by a central authority might not be possible or could be resource demanding. Attribute Based Encryption (ABE) is a recent cryptographic primitive which is being used for access control. We address some contemporary access control problems in distributed systems such as mobile ad hoc networks, vehicular networks, smart grids and cloud computing. Each of these applications has different constraints and requirements. We show how ABE and different variants of it can be tailored to suit the specific needs of the above applications.

Detecting misbehavior (such as transmissions of false information) in vehicular ad hoc networks (VANETs) is a very important problem with wide range of implications, including safety related and congestion avoidance applications. We discuss several limitations of existing misbehavior detection schemes (MDS) designed for VANETs. Most MDS are concerned with detection of malicious nodes. In most situations, vehicles would send wrong information because of selfish reasons of their owners, e.g. for gaining access to a particular lane. It is therefore more important to detect false information than to identify misbehaving nodes. We introduce the concept of data-centric misbehavior detection and propose algorithms which detect false alert messages and misbehaving nodes by observing their actions after sending out the alert messages. With the data-centric MDS, each node can decide whether an information received is correct or false. The decision is based on the consistency of recent messages and new alerts with reported and estimated vehicle positions. No voting or majority decisions is needed, making our MDS resilient to Sybil attacks. After misbehavior is detected, we do not revoke all the secret credentials of misbehaving nodes, as done in most schemes. Instead, we impose fines on misbehaving nodes (administered by the certification authority), discouraging them to act selfishly. This reduces the computation and communication costs involved in revoking all the secret credentials of misbehaving nodes.

We consider sensor self-deployment problem, constructing FOCUSED coverage (F-coverage) around a Point of Interest (POI), with novel evaluation metric, coverage radius. We propose to deploy sensors in polygon layers over a locally computable equilateral triangle tessellation (TT) for optimal F-coverage formation, and introduce two types of deployment polygon, H-polygon and C-polygon. We propose two strictly localized solution algorithms, Greedy Advance (GA), and Greedy-Rotation-Greedy (GRG). The two algorithms drive sensors to move along the TT graph to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI along locally computed H- or C-polygon to a vertex where greedy advance can resume. We prove that they both yield a connected network with maximized hole-free area coverage. To our knowledge, they are the first localized sensor self-deployment algorithms that provide such coverage guarantee. We further analyze their coverage radius property. Our study shows that GRG guarantees optimal or near optimal coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

IT is my pleasure to announce the creation of the IEEE Transactions on Parallel and Distributed Systems’ (TPDS) Media Center. We hope that the center will attract more readers to the journal, and assist our readers by facilitating their introduction to the latest development in the fi eld, ranging from the design of systems used in some contributions, new exciting technologies, to demonstrating new networking paradigms and solution approaches in the fi eld. It should further promote “systems” content in TPDS as opposed to traditionally prevailing “networking” content, although the latter is by no means excluded from the center. I have appointed new Associate Editor-in-Chief, Yunhao Liu, to handle the TPDS Media Center, together with his associates. He is involved in sensor network and RFID system constructions from hardware design through application development, and has a number of research contributions arising from these systems, primarily on localization, routing, operating systems, network diagnosis and management, and security. He is the principal scientist for the GreenOrbs project www.greenorbs.org in the TianMu mountain and urban sensor network in WuXi, China, each with more than 1,000 deployed sensors (collecting various sensory data, including temperature, humidity, illumination, and carbon dioxide titer), currently the two largest sensor deployments in the world. Yunhao Liu is among the top 10 author contributors to TPDS, and served as a TPDS associate editor before this appointment. His biography appears on the next page and contains a number of distinguished achievements. The TPDS Media Center is designed as a multimedia webpage for this scholarly archival journal. In the Media Center, TPDS will interview outstanding researchers or engineers for their experiences and opinions on a variety of theoretical or technological topics. Meanwhile, we warmly welcome and encourage editors, authors, or volunteers to share and advertise their state-of-the-art projects or ongoing research studies relevant to the topic of parallel and distributed systems through this Media Center. Activities and call for papers (or special issues) of TPDS will be announced through this multimedia platform as well. Each article in the Media Center is in the form of a blog composed by some multimedia content, like a video and audio clip, as the main medium, and supported by certain brief text descriptions. We hope to leverage such brand new features of the Media Center as a driving force for worldwide researchers to contribute high quality and live research results to the community. We hope that you can actively participate in its growth and make it a great success. In order to facilitate the contribution from peer researchers, we have set up an executing board of the Media Center to handle the content submissions from peer researchers. While the current board includes the Assistant EIC, Yunhao Liu (Professor at Tsinghua University, [email protected]), Executive Chair, Mo Li (Assistant Professor at Nanyang Technological University, Singapore, [email protected]), and the assistant, Zhenjiang Li ([email protected]), we will look for the expertise review opinions and inputs from the TPDS AEs as well as the research community. There are two categories of multimedia content that you can contribute. 1) The authors of an accepted regular TPDS paper are encouraged to submit their multimedia content along with their TPDS paper, which we will later select and publish on the media center. 2) Meanwhile, readers are also encouraged to directly submit their content to the executive chair Mo Li ([email protected]). We’ve provided an FTP site (ftp://transMedia:[email protected]) to receive the submission of multimedia contents, or you can fi rst publish the submission to some other places (Youtube, your own FTPs, etc.) and send the content links to us. TPDS has resolved its backlog issue, and papers are now published within approximately six months from their acceptance. To meet our annual page budget for 2012, page limit for the main fi le for most papers is back to its maximum, 14 pages. Each paper is still divided into two fi les, the main fi le (which replaces previously called “shortened version”) and the supplementary fi le. TPDS also resumed with organizing special issues. In 2011, calls for papers for two special issues were advertised, one on cyber-physical systems and another on cloud computing. I welcome proposals for future special issues. I take this opportunity to welcome and introduce new distinguished researchers to the Editorial Board of TPDS. Song Guo, David Kaeli, Bronis R. de Supinski, and Kui Wu were appointed as new Associate Editors, starting September 2011, while Manuel E. Acacio joined the board earlier, in April 2011. Their short biographies and areas of research are given below. I am confi dent they will contribute to further enhancing the quality and timelines of TPDS. Fabrizio Petrini, Masafumi Yamashita, John Lui, Sampath Rangarajan, and Cheng-Zhong Xu completed their four-year terms as TPDS editors in September 2011. Their help and dedication in processing papers is greatly appreciated.

We propose localized, self organizing, robust, and energy-efficient data aggregation tree approaches for sensor networks, which we call Localized Power-Efficient Data Aggregation Protocols (L-PEDAPs). They are based on topologies, such as LMST and RNG, that can approximate minimum spanning tree and can be efficiently computed using only position or distance information of one-hop neighbors. The actual routing tree is constructed over these topologies. We also consider different parent selection strategies while constructing a routing tree. We compare each topology and parent selection strategy and conclude that the best among them is the shortest path strategy over LMST structure. Our solution also involves route maintenance procedures that will be executed when a sensor node fails or a new node is added to the network. The proposed solution is also adapted to consider the remaining power levels of nodes in order to increase the network lifetime. Our simulation results show that by using our power-aware localized approach, we can almost have the same performance of a centralized solution in terms of network lifetime, and close to 90 percent of an upper bound derived here.

Abstract Vehicular networks are envisioned for large scale deployment, and standardization bodies, car manufacturers, and academic researchers are solving a variety of related challenges. After a brief description of intelligent transportation system (ITS) architectures and the main already‐established low‐level standards, this tutorial elaborates on four particular aspects of vehicular networks, which are (i) the potential for a large set of innovative applications, (ii) a review of the main modeling approaches used for both roads and traffic, and finally two important communication primitives, that are (iii) data disseminationviabroadcasting/geocasting, and (iv) routing in both highway and urban environments. A particular emphasis is on recent protocols that realistically consider the inherently complex nature of vehicular mobility, such as intermittent connectivity, speed variability, and the impact of intersections. Copyright © 2009 John Wiley & Sons, Ltd.

ABSTRACT In data aggregation, sensor measurements from the whole sensory field or a sub‐field are collected as a single report at an actor by using aggregate functions such as sum, average, maximum, minimum, count, deviation, and so on. We propose a localized delay‐bounded and energy‐efficient data aggregation (DEDA) protocol for request‐driven wireless sensor networks with IEEE 802.11 carrier sense multiple access with collision avoidance run at media access control layer. This protocol uses a novel two‐stage delay model, which measures end‐to‐end delay by using either hop count or degree sum along a routing path depending on traffic intensity. It models the network as a unit disk graph (UDG) and constructs a localized minimal spanning tree (LMST) sub‐graph. Using only edges from LMST, it builds a shortest‐path (thus energy‐efficient) tree rooted at the actor for data aggregation. The tree is used without modification if it generates acceptable delay, compared with a given delay bound. Otherwise, it is adjusted by replacing LMST sub‐paths with UDG edges. The adjustment is done locally on the fly, according to the desired progress value computed at each node. We further propose to integrate DEDA with a localized sensor activity scheduling algorithm and a localized connected dominating set algorithm, yielding two DEDA variants, to improve its energy efficiency and delay reliability. Through an extensive set of simulation, we evaluate the performance of DEDA with various network parameters. Our simulation results indicate that DEDA far outperforms the only existing competing protocol. Copyright © 2011 John Wiley & Sons, Ltd.

We introduce a novel combinatorial optimization problem: the one-commodity traveling salesman problem with selective pickup and delivery (1-TSP-SELPD), characterized by the fact that the demand of any delivery customer can be met by a relatively large number of pickup customers. While all delivery spots are to be visited, only profitable pickup locations will be included in the tour so as to minimize its cost. The motivation for 1-TSP-SELPD stems from the carrier-based coverage repair problem in wireless sensor and robot networks, wherein a mobile robot replaces damaged sensors with spare ones. The ant colony optimization (ACO) meta-heuristic elegantly solves this problem within reasonable time and space constraints. Six ACO heuristic functions are put forward and a recently proposed exploration strategy is exploited to accelerate convergence in dense networks. Results gathered from extensive simulations confirm that our ACO-based model outperforms existing competitive approaches.

Nodes in contention-based (beaconless) georouting forward packets towards a known destination position without the knowledge of the neighborhood. The only existing methods [17], [20] that guarantee delivery in unit disk graphs (UDG) require runtime planarization of the communication graph with either unbounded message overhead per hop while preserving the Gabriel graph property of the subgraph, or a constant overhead per hop with up to 13 control messages. In this paper we show that the next hop can be selected directly by a contention mechanism and without prior planarization. Existing greedy routing methods select the next hop with 3 messages using a RTS-CTS-DATA scheme in a timer-based contention where only the next hop neighbor responds. We extend this to provide also recovery from local minima with 3 messages per hop by the Rotational Sweep algorithm. We prove that our algorithm guarantees delivery in UDGs, and also yields routes that are shorter than or equal to the combined greedy and face routing with Gabriel graph planarization. Simulation results show that especially the duration of the contention process can be significantly reduced. Our algorithm can be also used for conventional beacon-based routing with guaranteed delivery without prior planarization, replacing the complicated implementation from [19] by a very simple method which evaluates angular distances to select the proper forwarding neighbor. It also provides a simple network boundary detection algorithm, with or without beacons.

We propose a novel localized carrier-based sensor placement algorithm, named Back-Tracking Deployment (BTD). Mobile robots (carriers) carry static sensors and drop them at visited empty vertices of a virtual square, triangular or hexagonal grid in a bounded 2D environment. A single robot will move forward along the virtual grid in open directions with respect to a pre-defined order of preference until a dead end is reached. Then it back tracks to the nearest sensor adjacent to an empty vertex on its backward path. The robot resumes regular forward moving and sensor dropping from there. To save movement steps, the back tracking is performed along a locally identified shortcut. We extend the algorithm to support multiple robots, which move independently and asynchronously. Once a robot reaches a dead end, it will back-track, giving preference to its own path. Otherwise it will take over the back-track path of another robot, by consulting with neighboring sensors. We prove that BTD terminates in finite time and produces full coverage when no sensor failures occur. We also describe an approach to handle sensor faults. Through extensive simulation we show that BTD far outperforms the only competing algorithm LRV in robot moves and robot messages.

This paper proposes a new solution to the problem of self-deploying a network of wireless mobile robots with simultaneous consideration to several criteria, that are, the fault-tolerance (biconnectivity) of the resulting network, its coverage, its diameter, and the quantity of movement required to complete the deployment. These criteria have already been addressed individually in previous works, but we propose here an elegant solution to address all of them at once. Our approach is based on combining two complementary sets of virtual forces: spring forces, whose properties are well known to provide optimal coverage at reasonable movement cost, and angular forces, a new type of force proposed here whose effect is to rotate two angularly consecutive neighbors toward one another when the corresponding angle is larger than 60° (even if these nodes are not direct neighbors). Angular forces have the global effect of biconnecting the network and reducing its diameter, while not affecting the benefits obtained by spring forces on coverage. In this paper we give a detailed description of the combination of both types of forces. We also provide an implementation relying only on position exchanges within two hops. Simulations results are finally presented to evaluate our solution with respect to the four considered criteria (coverage, biconnectivity, quantity of movements, and diameter), and compare it with prior approaches.

In wireless sensor networks (WSN), stochastic node dropping and unpredictable node failure greatly impair coverage, creating sensing holes, while locally redundant sensors exist. If sensors are all equipped with locomotion, they will be able to relocate themselves to improve coverage. But this approach increases the complexity of hardware design for sensors as well as deployment budget. In this paper, we consider a small group of mobile robots to serve WSN. We propose an algorithm, named Randomized Robot-assisted Relocation of Static Sensors (R3S2), for coverage repair and a grid-based variant, called G-R3S2. By these algorithms, mobile robots move within the network to collect redundant sensors and deliver them to reported sensing hole positions. In R3S2, robots move completely at random and relocate encountered redundant sensors. In G-R3S2, the robots random movement is restricted on a virtual grid, and the robots continually move to the next least recently visited grid point so as to increase the chance of discovering redundant sensors and sensing holes. Through extensive simulation, we show their effectiveness and practicality and evaluate their performance. The simulation results indicate in particular that G-R3S2 outperforms R3S2 across all measured metrics.

The 25 papers in this special issue focus on simple wireless sensor networking solutions.

In this paper, we provide a thorough theoretical study on delivery guarantees, loop-free operation, and worst-case behavior of face and combined greedy-face routing. We show that under specific planar topology control schemes, recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary planar graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. We provide complete and formal proofs that several proposed face routing and combined greedy-face routing schemes guarantee message delivery in specific planar graph classes or even in arbitrary planar graphs. We also discuss the reasons why other methods fail to deliver a message or even end up in a loop. In addition, we investigate the behavior of face routing in arbitrary not necessarily planar networks and show, while delivery guarantees cannot be supported in such a general case, most face and combined greedy-face routing variants support at least loop-free operation. For those variants, we derive worst-case upper bounds on the number of forwarding steps.

WRITING contributions in a form that other people can understand is a very slow process. The purpose of this editorial is to serve as a guideline for making research presentations as easy to comprehend as absolutely possible. Perceived simplicity of any original idea is its ultimate advantage. The key advice to a successful presentation is to repeat the description of main contribution four times: in the title, abstract, introduction, and text. That is, to make readable, appealing, and as complete as possible versions of the work using the order of 10, 100, 1,000 and 10,000 words. Each of them should be self-contained and complete to the greatest possible extent. This corresponds to the decreasing portion of readers for corresponding parts of the article. To the extent possible, each of these parts should address, in this order: the problem statement, existing solutions, the new solution(s), assumptions and limitations, analysis, simulation, and comparison with the best competing solutions. Research is a problem solving exercise, differing it from development, implementation, or another type of work. Consequently, any research article should make a clear problem statement. The selected title of an article should describe the main contribution and the essence of the basic ideas used. The abstract is the most important part of a research article. Instead of listing topics covered in the article, the abstract should convey the essential information found in the paper. The author should make an effort to claim the contribution properly at the most visible place, in the abstract. It should have the following structure (each part with flexible length):

Focused coverage is defined as the coverage of a wireless sensor network surrounding a point of interest (POI), and is measured by coverage radius, i.e., minimum distance from POI to uncovered areas. Sensor self-deployment algorithm GRG is designed for autonomous focused coverage formation. It however does not always produce optimal (i.e., maximized) coverage radius. In this paper, we propose optimized GRG, referred to as OGRG, for guaranteed coverage radius maximization, and evaluate its performance in comparison with GRG.

In the anycasting problem, a sensor wants to report event information to one of sinks or actors. We describe the first localized anycasting algorithms that guarantee delivery for connected multi-sink sensor-actor networks. Let S(x) be the closest actor/sink to sensor x, and |xS(x)| be distance between them. In greedy phase, a node s forwards the packet to its neighbor v that minimizes the ratio of cost cost(|sv|) of sending packet to v (here we specifically apply hop-count and power consumption metrics) over the reduction in distance (|sS(s)|-|vS(v)|) to the closest actor/sink. A variant is to forward to the first neighbor on the shortest weighted path toward v. If none of neighbors reduces that distance then recovery mode is invoked. It is done by face traversal toward the nearest connected actor/sink, where edges are replaced by paths optimizing given cost. A hop count based and two variants of localized power aware anycasting algorithms are described. We prove guaranteed delivery property analytically and experimentally.

We pinpoint a new sensor self-deployment problem, constructing focused coverage around a point of interest (POI), and introduce an evaluation metric, coverage radius. We propose two solutions, greedy advance (GA) and greedy-rotation-greedy (GRG), which are to our knowledge the first sensor self-deployment algorithms that operate in a purely localized manner and yet provide coverage guarantee. The two algorithms drive sensors to move along a locally-computed equilateral triangle tessellation (TT) to surround POI. In GA, nodes greedily proceed as close to POI as they can; in GRG, when their greedy advance is blocked, nodes rotate around POI to a TT vertex where greedy advance can resume. They both yield a connected network of TT layout with hole-free coverage; GRG furthermore assures a hexagon coverage shape centered at POI. We prove their correctness and analyze their coverage radius property. Our study shows that GRG guarantees optimal hexagonal coverage radius and near optimal circular coverage radius. Through extensive simulation we as well evaluate their performance on convergence time, energy consumption, and node collision.

Existing theoretical and simulation studies on georouting appear detached from experimental studies in real environments. We set up our test environment by using WSN430 wireless sensor nodes. To overcome the need for significant number of wireless nodes required to perform a realistic experiment in high density network, we introduce a novel approach - emulation by using relatively small number of nodes in 1-hop experimental setup. Source node is a fixed sensor, all available sensors are candidate forwarding neighbors with virtual destination. Source node makes one forwarding step, destination position is adjusted, and the same source again searches for best forwarder. We compare three georouting algorithms. We introduce here greedy geographical routing algorithms in a real environment (GARE) which builds a RNG by using ETX(uv)/|uv| as edge weight (ETX(uv) counts all transmissions and possibly acknowledgments between two nodes until message is received), and selects RNG neighbor with greatest progress toward destination (if none of RNG neighbors has progress, all neighbors are considered). Our experiments show that GARE is significantly more efficient than existing XTC algorithm (applying RNG on ETX(uv)) in energy consumption. COP GARE selects neighbor with progress that minimizes ETX(uv)/|uv|, and outperforms both algorithms.

We consider multiple source asynchronous broadcasting problem. That is, in each broadcast, one of the nodes is the source, and the message is to be received, unaltered, by all the other nodes in the network. We propose to exploit LT code, which is one of the fountain codes, with the source independent backbone in order to reduce the number of transmissions for broadcasting with network coding in ad hoc wireless network. We use the principle of LT code to perform network coding in a simple distributed manner where encoding can be applied with both received singletons and non-singletons, and generated candidates can be used in an optimization criteria. We show by simulation that our approach reduces the number of transmissions required for flooding.

Most of the envisioned services over vehicular networks need to deliver information to all vehicles inside a certain region. Several such broadcasting protocols have been reported so far, but surprisingly only one of them addresses the issue of intermittent connectivity. In this paper, we present a broadcast protocol which is suitable for a wide range of vehicular scenarios and traffic conditions. The protocol employs local position information acquired via periodic beacon messages. Beacons are used by cars to decide whether or not they belong to a connected dominating set (CDS). Vehicles in the CDS use shorter waiting period before possible retransmissions. Identifiers of circulated broadcast messages are added to beacons as piggybacked acknowledgements. When waiting timeout expires, vehicle retransmits if it has at least one neighbor which did not acknowledge circulated message with the last beacon, and sets a new waiting period. Our algorithm does not depend on any parameter or threshold which varies its operation. Despite its simplicity, the protocol is shown to provide high reliability and efficiency by means of a simulation-based performance evaluation. It also greatly outperforms the only competing algorithm we found in the literature which explicitly considers different mobility scenarios.

We propose several localized algorithms to achieve energy-efficient broadcasting in wireless multihop networks using directional antennas. Each node needs to know only geographic position of itself and its neighbors. Our first protocol is called DRBOP and it follows the one-to-one communication model to reach to all nodes in the relative neighborhood graph (RNG). Each node that receives a message for the first time from one of its RNG neighbors will rebroadcast it to each of its remaining RNG neighbors separately. The transmission power is adjusted for each transmission to the minimal necessary for reaching the particular neighbor. Next, we describe DLBOP, where RNG is replaced by the localized minimum spanning tree (LMST) graph which is a localized topology resembling the minimum spanning tree. We then observe that, for very dense networks, it is more energy-efficient to reach more than one neighbor at a time. A one-to-many protocol efficient for dense networks is proposed. We then describe an efficient localized protocol which adaptively switches (without any threshold) between one-to-one and one-to-many communication models and is efficient for both sparse and dense networks. Our simulation results show that for different energy models, the adaptive protocol is able to achieve a competitive performance to globalized algorithms while having a fully localized operation.

We formalize the distance-sensitive service discovery problem in wireless sensor and actor networks, and propose a novel localized algorithm, iMesh. Unlike existing solutions, iMesh uses no global computation and generates constant per-node storage load. In iMesh, new service providers (i.e., actors) publish their location information in four directions, updating an information mesh. Information propagation for relatively remote services is restricted by a blocking rule, which also updates the mesh structure. Based on an extension rule, nodes along mesh edges may further advertise newly arrived relatively near service by backward distance-limited transmissions, replacing previously closer service location. The final information mesh is a planar structure constituted by the information propagation paths. It stores locations of all the service providers and serves as service directory. Service consumers (i.e., sensors) conduct a lookup process restricted within their home mesh cells to discover nearby services. We analytically study the properties of iMesh including construction cost and distance sensitivity over a static network model. We evaluate its performance in static/dynamic network scenarios through extensive simulation. Simulation results verify our theoretical findings and show that iMesh guarantees nearby (closest) service selection with very high probability, Gt99 percent (respectively, Gt95 percent).

In a broadcasting task, source node wants to send the same message to all the other nodes in the network. Existing solutions range from connected dominating set (CDS) based for static networks, to blind flooding for moderate mobility, to hyperflooding for highly mobile and frequently partitioned networks. The only existing protocol for all scenarios is based on some threshold parameters (which may be expensive to gather) to locally select between these three solution approaches. Here we propose a new protocol, which adjusts itself to any mobility scenario without using any parameter. Unlike existing methods for highly mobile scenarios, in proposed method, two nodes do not transmit every time they discover each other as new neighbors. Each node maintains a list of two hop neighbors by periodically exchanging 'hello' messages, and decides whether or not it is in CDS. Upon receipt of the first copy of message intended for broadcasting, it selects a waiting timeout and constructs two lists of neighbors: neighbors that received the same message and neighbors that did not receive it. Nodes not in CDS select longer timeouts than nodes in CDS. These lists are updated upon receipt of further copies of same packet. When timeout expires, node retransmits if the list of neighbors in need of message is nonempty. 'Hello' messages received while waiting, or after timeout expiration may revise all lists (and CDS status) and consequently the need to retransmit. This provides a seamless transition of protocol behavior from static to highly mobile scenarios. Our protocol is compared to existing solutions. It was shown to be superior to all of them in number of retransmissions and reliability.

Bluetooth standard allows the creation of piconets, with one node serving as its master and up to seven nodes serving as slaves. A Bluetooth ad hoc network can also be formed by interconnecting several piconets into a scatternet. Given a set of Bluetooth nodes which are positioned so that their unit disk graph is connected, the Bluetooth scatternet formation (BSF) problem is to select piconets, and master and slave roles in each piconet, so that the obtained scatternet is connected, has some desirable properties and good performance with respect to some metrics. In this article we propose BSF protocol based on maximal independent sets. It is a two iterations protocol. In the first iteration a piconet containing a maximal independent set is constructed for every device, while the second iteration attempts to simplify the scatternet structure and to delete piconets not essential for the connectivity. A major advantage of this novel protocol is its simplicity. Simulations show its advantage over the best competing protocol and especially for moderately dense networks.

Recently proposed beaconless georouting algorithms are fully reactive, with nodes forwarding packets without prior knowledge of their neighbors. However, existing approaches for recovery from local minima can either not guarantee delivery or they require the exchange of complete neighborhood information. We describe two general methods that enable completely reactive face routing with guaranteed delivery. The Beaconless Forwarder Planarization (BFP) scheme finds correct edges of a local planar subgraph at the forwarder node without hearing from all neighbors. Face routing then continues properly. Angular Relaying determines directly the next hop of a face traversal. Both schemes are based on the Select and Protest principle. Neighbors respond according to a delay function, if they do not violate the condition for a planar subgraph construction. Protest messages are used to remove falsely selected neighbors that are not in the planar subgraph. We show that a correct beaconless planar subgraph construction is not possible without protests. We also show the impact of the chosen planar subgraph construction on the message complexity. This leads to the definition of the Circlunar Neighborhood Graph (CNG), a new proximity graph, that enables BFP with a bounded number of messages in the worst case, which is not possible when using the Gabriel graph (GG). The CNG is sparser than the GG, but this does not lead to a performance degradation. Simulation results show similar message complexities in the average case when using CNG and GG. Angular Relaying uses a delay function that is based on the angular distance to the previous hop. Simulation results show that in comparison to BFP more protests are used, but overall message complexity can be further reduced.

Vehicular ad hoc networks (VANET) have recently received increasing attention in the media. And with good reason: VANET promises to integrate driving into a ubiquitous and pervasive network that will redefine the way we live and work.

This paper considers the problem of designing power efficient routing with guaranteed delivery for sensor networks with known distances between neighbors but unknown geographic locations. We propose Hector, a hybrid energy efficient tree-based optimized routing protocol, based on two sets of virtual coordinates. One set is based on rooted tree coordinates, and the other is based on hop distances toward several landmarks. In our algorithm, the node currently holding the packet forwards it to its neighbor that optimizes ratio of power cost over distance progress with landmark coordinates, among nodes that reduce landmark coordinates and do not increase tree coordinates. If such a node does not exist then forwarding is made to the neighbor that reduces tree based distance and optimizes power cost over tree distance progress ratio. Our simulations show the superiority of our algorithm over existing alternatives while guaranteeing delivery, and only up to 30% additional power compared to centralized shortest weighted path algorithm.

We propose several localized sensor area coverage protocols for heterogeneous sensors, each with arbitrary sensing and transmission radii. Sensors are assumed to be time synchronized, and active sensors are determined at the beginning of each round. The approach has a very small communication overhead since prior knowledge about neighbor existence is not required. Each node selects a random timeout and listens to messages sent by other nodes before the timeout expires. Sensor nodes whose sensing area is not fully covered (or fully covered but with a disconnected set of active sensors) when the deadline expires decide to remain active for the considered round, and transmit an activity message announcing it. There are four variants in our approach, depending on whether or not withdrawal and retreat messages are transmitted. Covered nodes decide to sleep, with or without transmitting withdrawal message to inform neighbors about the status. After hearing from more neighbors, active sensors may observe that they became covered, and may decide to alter their original decision and transmit a retreat message. Our simulation shows reduced message overhead while preserving coverage quality compared to existing method based on hello messages followed by retreat ones.

In this paper we propose a distributed, self organizing, robust and energy efficient data gathering algorithm for sensor networks operating in environments where all the sensor nodes are not in direct communication range of each other and data aggregation is used while routing. Proposed algorithm is based on local minimum spanning tree (LMST) structure, which nodes can construct from the position of their 1-hop neighbors. Reporting tree is constructed from the sink by allowing only edges of LMST to join the tree, plus possibly some direct links to the sink. Each node selects as parent the LMST neighbor so that the total energy cost of route to the sink is minimal. We also describe route maintenance protocols to respond to predicted sensor failures and addition of new sensors. Our simulation results show that our algorithm prolongs the network lifetime significantly compared to some alternative schemes.

Ad hoc, actuator and sensor wireless networks normally have critical connectivity properties before becoming fault intolerant. Existing algorithms for testing k-connectivity are centralized. In this article, we introduce localized algorithms for testing A-connectivity. In localized protocols, each node makes its own decision based on the information available in its local neighborhood. In the first proposed local neighbor detection (LND) algorithm, each node verifies whether or not itself and each of its p-hop neighbors have at least k neighbors. In the second local critical node detection (LCND) protocol, it also tests if the subgraph of its p-hop neighbours of a given node is k-connected. The third local subgraph connectivity detection (LSCD) protocol is based on communications between neighboring nodes to exchange the local decisions starting from k=l. All nodes declare themselves locally 1-connected. For k=2,3,..., iteratively, local decisions are propagated to p-hop neighbors. If node A is (k-1,)-connected, all its p-hop neighbors are (k-1)-connected, and the graph consisting of p-hop neighbors of A (excluding A) is (k-1,)-connected, then node A declares its neighborhood as k-connected. The experiments are carried with two ways of uniform generation of connected unit disk graphs. They show low percentage of false 'alarms', ability to locate critical areas in k-disconnected networks, and increased accuracy with increased local knowledge.

We assume that sensors are aware of the positions of neighbors within a specific knowledge range, which is smaller than their maximum transmission range. We propose the GRoVar protocol (Geographic Routing with Variable transmission range) that extends the well-known GFG protocol [2], a combination of greedy forwarding and recovery, by applying variable transmission range and beaconless routing techniques. In our protocol, each node locally selects the best forwarding neighbor within its knowledge range, using power or other metric. If no neighbor is closer to the destination, the current node may incrementally increase its transmission range to find suitable candidates for the next hop, with the help of request messages. Face routing is applied when no forwarding neighbor is found after sending requests with the maximum transmission range. It also applies range increases until recovery is possible. We investigated different possibilities: a linear increase, doubling the range in each iteration or directly jumping to the maximum range possible. The comparison of energy usage for data transfer from source to sink shows that a significant saving in energy consumption can be achieved using the proposed method.

In this paper, we consider graphs created by actuators (people, robots, vehicles etc.) in sensor-actuator networks. Most simulation studies for wireless ad hoc and sensor networks use connected random unit disk graphs generated by placing nodes randomly and independently from each other. However, in real life networks are created by actuators in a cooperative manner. Usually certain restrictions are imposed during the placement of a new node in order to improve network connectivity and functionality. This article is an initial study on how connected actuator graphs (CAG) can be generated by fast algorithms and what kind of desirable characteristics can be achieved compared to completely random graphs, especially for sparse node densities. We describe several CAG generation schemes where the next node (actuator) position is selected based on the distribution of the nodes already placed. In our Minimum Degree Proximity algorithm (MIN-DPA), a new node is placed to be a neighbor of an existing node with the lowest degree (number of neighbors). In our Maximum Degree Proximity algorithm (MAX-DPA), a new node cannot be placed to increase the degree of any existing node over a pre-specified parameter limit. We show that these new algorithms are significantly faster than the well-known random unit graph generation scheme for sparse graphs. The graphs generated by these new schemes are not necessarily drawn from the same distribution as those generated by the independent node placement. Thus, we explore their properties by studying their average node degree and partition patterns.

Abstract — This paper investigates theoretical aspects of the uneven energy depletion phenomenon recently noticed in sink-based wireless sensor networks. We consider uniformly distributed sensors, each sending roughly the same number of reports toward the closest sink. We assume an energy consumption model governed by the relation E = dα +c where d, (d ≤ tx), is the transmission distance, α ≥ 2 is the power attenuation, c is a technology-dependent positive constant, and tx is the maximum transmission range of sensors. Our results are multifold. First, we show that for α> 2, all sensors whose distance to the sink is min{tx, ( 2c 1 α−2) α} should transmit directly to the sink. Interestingly, this limit does not depend on the size of the network, expressed as the largest distance R from a sensor to the closest sink. Next, we prove that in order to minimize the total amount of energy spent on routing along a path originating at a sensor in a corona and ending at the sink, all the coronas must have the same width, equal to the above expression. This choice, however, leads to uneven energy depletion and to the creation of energy holes. We show that for α>2 the uneven energy depletion can be prevented by judicious system design, resulting in balanced energy expenditure across the network. We describe an iterative process for determining the sizes of coronas. Their optimal sizes (and corresponding transmission radii) and the number of coronas depend on R. As expected, the width of coronas in energy-balanced sensor network increases. Finally, we show that for α =2, the uneven energy depletion phenomenon is intrinsic to the system and no routing strategy can avoid the creation of an energy hole around the sink. I.

Location service provides position of mobile destination to source node to enable geo-routing. Previous location service protocols suffer from partial flooding overhead, and/or location failures in group movement scenarios. To overcome those deficiencies, we propose a quorum-based location service. The basic idea is that destination node registers its location along a `column' to form an update quorum. Source node makes a query along a `row' to form a search quorum. The destination location is found at the intersection between the update and search quorums. Four strategies are proposed to adjust the quorum system. To guarantee the success of location retrieval, both search and update quorums are extended by face routing which traverses outer network boundary

It was recently reported that all known face and combined greedy-face routing variants cannot guarantee message delivery in arbitrary undirected planar graphs. The purpose of this article is to clarify that this is not the truth in general. We show that specifically in relative neighborhood and Gabriel graphs recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. A prominent approach is to visit a sequence of faces which are intersected by the line connecting the source and destination node. Whenever encountering an edge which is intersecting with this line, the critical part is to decide if face traversal has to change to the next adjacent one or not. Failures may occur from incorporating face routing procedures that force to change the traversed face at each intersection. Recently observed routing failures which were produced by the GPSR protocol in arbitrary planar graphs result from incorporating such a face routing variant. They cannot be constructed by the well known GFG algorithm which does not force changing the face anytime. Beside methods which visit the faces intersected by the source destination line, we discuss face routing variants which simply restart face routing whenever the next face has to be explored. We give the first complete and formal proofs that several proposed face routing, and combined greedyface routing schemes do guarantee delivery in specific graph classes or even any arbitrary planar graphs. We also discuss the reasons why other methods may fail to deliver a message or even end up in a loop.

We propose several localized sensor area coverage protocols, for arbitrary ratio of sensing and transmission radii. Sensors are assumed to be time synchronized, and active sensors are determined at the beginning of each round. The approach has a very small communication overhead since prior knowledge about neighbor existence is not required. Each node selects a random timeout and listens to messages sent by other nodes before the timeout expires. Sensor nodes whose sensing area is not fully covered (or fully covered but with a disconnected set of active sensors) when the deadline expires decide to remain active for the considered round, and transmit a message announcing their activity status. There are four variants in our approach, depending on whether or not negative and retreat messages are transmitted. Experimental results with ideal MAC layer show that, for a similar number of selected active sensors, our methods significantly reduce number of messages to decide activity compared to existing localized protocol, we also consider a MAC layer with collisions, and show that existing compared method, for dense networks, fails to cover the area reasonably. Our methods, however, still remain robust in terms of high area coverage with reasonable amount of active nodes, despite some message collisions.

We present geographic multicast routing (GMR), a new multicast routing protocol for wireless sensor networks. GMR manages to preserve the good properties of previous geographic unicast routing schemes while being able to efficiently deliver multicast data messages to multiple destinations. It is a fully-localized algorithm (only needs information provided by neighbors) and it does not require any type of flooding throughout the network. Each node propagating a multicast data message needs to select a subset of its neighbors as relay nodes towards destinations. GMR optimizes cost over progress ratio. The cost is equal to the number of selected neighbors, while progress is the overall reduction of the remaining distances to destinations. That is, the difference between distance from current node to destinations and distance from selected nodes to destinations. Such neighbor selection achieves a good trade-off between the cost of the multicast tree and the effectiveness of the data distribution. Our cost-aware neighbor selection is based on a greedy set merging scheme achieving a O(Dn min(D, n)3) computation time, where n is the number of neighbors of current node and D is the number of destinations. This is superior to the exponential computational complexity of an existing solution (PBM) which tests all possible subsets of neighbours, and to an alternative solution that we considered, tests all the set partitions of destinations. Delivery to all destinations is guaranteed by applying face routing when no neighbor provides advance toward certain destinations. Our simulation results show that GMR outperforms previous multicast routing schemes in terms of cost of the trees and computation time over a variety of networking scenarios. In addition, GMR does not depend on the use of any parameter, while the closest competing protocol has one parameter and remains inferior for all values of that parameter

We investigate the problem of minimum energy broadcasting in ad hoc networks where nodes have capability to adjust their transmission range. The minimal transmission energy needed for correct reception by neighbor at distance r is proportional to r/sup /spl alpha//+c/sub e/, /spl alpha/ and c/sub e/ being two environment-dependent constants. We demonstrate the existence of an optimal transmission radius, computed with a hexagonal tiling of the network area, that minimizes the total power consumption for a broadcasting task. This theoretically computed value is experimentally confirmed. The existing localized protocols are inferior to existing centralized protocols for dense networks. We present two localized broadcasting protocols, based on derived "target" radius, that remain competitive for all network densities. The first one, TR-LBOP, computes the minimal radius needed for connectivity and increases it up to the target one after having applied a neighbor elimination scheme on a reduced subset of direct neighbors. In the second one, TRDS, each node first considers only neighbors whose distance is no greater than the target radius (which depends on the power consumption model used), and neighbors in a localized connected topological structure such as RNG or LMST. Then, a connected dominating set is constructed using this subgraph. Nodes not selected for the set may be sent to sleep mode. Nodes in selected dominating set apply TR-LBOP. This protocol is the first one to consider both activity scheduling and minimum energy consumption as one combined problem. Finally, some experimental results for both protocols are given, as well as comparisons with other existing protocols. Our analysis and protocols remain valid if energy needed for packet receptions is charged.

1 THE SCOPE WE are very proud and honored to have been entrusted to guest edit this special section. The main goal was to put together a strong issue emphasizing quality and relevance to current interests in this important field. Papers were sought to cover comprehensively the algorithmic issues in the “hot” area of ad hoc and sensor networking. The concentration was on the network layer problems which can be divided into two groups: data communication and topology control problems. In data communication problems, such as routing, quality-of-service routing, geocasting, multicasting, and broadcasting, the primary goal is to fulfill a given communication task successfully between nodes in an ad hoc network. The secondary task is to minimize the communication overhead and power consumption given that in the vast majority of applications nodes run on batteries. Topology control problems are further subdivided into neighbor discovery and network organization problems. In the neighbor discovery problem, the problem is to detect neighboring nodes located within transmission range. In the network organization problem, each node should decide what communication links to establish with neighboring nodes (an example is the Bluetooth scatternet formation problem), and what power management schemes to adopt (examples are “sleep” period operations and adjusting transmission ranges). Due to their theoretical challenges and myriads of practical applications, wireless sensor networks are emerging as one of the priority research and development areas. The applications of sensor networks are envisioned primarily for monitoring the environment (e.g., motion detection, chemicals, temperature) or as key components in embedded systems (e.g., biomedical sensor engineering). This special section also sought submissions on this “hot” topic, including problems such as: physical properties, sensor training, security through intelligent node cooperation, medium access, sensor area coverage with random and deterministic placement, object location, sensor position determination, energy efficient broadcasting and activity scheduling, routing, connectivity, data dissemination and gathering, sensor centric quality of routing, path exposure, tree reconfiguration, topology construction, and transport layer. The main paradigm shift is to apply localized schemes as opposed to existing protocols requiring global information. Localized algorithms are distributed algorithms where simple local node behavior achieves a desired global objective. Localized protocols provide scalable solutions, that is, solutions for wireless networks with an arbitrary number of nodes, which is the main goal of this plan. Sensor and rooftop/mesh networks, for instance, have hundreds or thousands of nodes.

Abstract In this paper, we propose a general algorithm (based on an unified framework for both routing and geocasting problems), in which message is forwarded to exactly those neighbors which may be best choices for a possible position of destination (using the appropriate criterion). We then propose and discuss new VD‐GREEDY and CH‐MFR methods and define R‐DIR, modified version of existing directional methods. In VD‐GREEDY method, these neighbors are determined by intersecting the Voronoi diagram of neighbors with the circle (or rectangle) of possible positions of destination, while the portion of the convex hull of neighboring nodes is analogously used in the CH‐MFR method. Routing and geocasting algorithms differ only inside the circle/rectangle. The proposed methods may be also used for the destination search phase allowing the application of different routing schemes after the exact position of destination is discovered. VD‐GREEDY and CH‐MFR algorithms are loop free, and have smaller flooding rate (with similar success rate) compared to directional method. We proposed to use dominating set concept to reduce flooding ratio significantly, with a marginal impact on success rate and hop count. Simulations, involving the proposed and some known algorithms, are performed for two basic scenarios, one for geocasting and reactive routing, and the other for proactive routing, and both showed that our methods have higher success rate and lower flooding rate compared to existing methods. Copyright © 2006 John Wiley & Sons, Ltd.

Summary form only given. In a broadcasting problem, a message is sent from a source to all the other nodes in the network. Blind flooding is a classical mechanism for broadcasting, where each node retransmits received message to all its neighbors. We propose a new broadcasting and searching scheme over the Internet based on generalized relative neighborhood graphs (RNG). Messages are forwarded only on RNG links, and a link is in RNG if and only if it is not the 'longest' edge in any triangle. We extend the existing definition of RNG, using geographic distance, to other metrics such as delay. RNG is a sparse connected structure based on local information at each node (distances to each neighbor and distances between neighbors). This new scheme is compared to the existing flooding, and rumor mongering (or gossip) schemes to evaluate its performance. Our parameterless RNG based scheme guarantees delivery to each node with considerably reduced number of messages with respect to flooding, and has comparable amount of message to rumor mongering/gossip scheme that does not guarantee delivery to each node and also uses parameters whose best value depend on underlying network density.

Existing routing and broadcasting protocols for ad hoc networks assume an ideal physical layer model. We apply the log-normal shadow fading model to represent a realistic physical layer and use the probability p(x) for receiving a packet successfully as a function of distance x between two nodes. We define the transmission radius R as the distance at which p(R)=0.5. We propose a medium access control layer protocol, where receiver node acknowledges packet to sender node u times, where u*p(x)/spl ap/1. We derived an approximation for p(x) to reduce computation time. It can be used as the weight in the optimal shortest hop count routing scheme. We then study the optimal packet forwarding distance to minimize the hop count, and show that it is approximately 0.73R (for power attenuation degree 2). A hop count optimal, greedy, localized routing algorithm [referred as ideal hop count routing (IHCR)] for ad hoc wireless networks is then presented. We present another algorithm called expected progress routing with acknowledgment (referred as aEPR) for ad hoc wireless networks. Two variants of aEPR algorithm, namely, aEPR-1 and aEPR-u are also presented. Next, we propose projection progress scheme, and its two variants, 1-Projection and u-Projection. Iterative versions of aEPR and projection progress attempt to improve their performance. We then propose tR-greedy routing scheme, where packet is forwarded to neighbor closest to destination, among neighbors that are within distance tR. All described schemes are implemented, and their performances are evaluated and compared.

We investigate minimum energy broadcasting problem where mobile nodes have the capability to adjust their transmission range. The power consumption for two nodes at distance r is r/sup /spl alpha// + c, where /spl alpha/ /spl ges/ 2 and c is a constant that includes signal processing and minimal reception power. We show that, for c > 0 (which is realistic assumption), it is not optimal to minimize transmission range. Furthermore, we demonstrate that there exists an optimal radius, computed with a hexagonal tiling of the network area that minimizes the power consumption. For /spl alpha/ > 2 and c > 0, the optimal radius is r = /spl alpha//spl radic/(2c//spl alpha/-2), which is derived theoretically, and confirmed experimentally. We propose also a localized broadcast algorithm TR-LBOP that takes this optimal radius into account. This protocol is experimentally shown to be efficient compared to existing localized protocol LBOP and globalized BIP protocol. Most importantly, TR-LBOP is shown to have limited energy overhead with respect to BIP for all network densities, which is not the case with LBOP whose overhead explodes for higher densities.

This work addresses the problem of scattemet formation for single-hop Bluetooth based personal area and ad hoc networks, with minimal communication overhead. Recent scatternet formation schemes by Li, Stojmenovic and Wang [Ref. 1] are position based and were applied for multihop networks. These schemes are localized and can construct degree limited and connected piconets, without parking any node. In this article we apply their methods to single-hop networks, by showing that position information is then not needed. Each node can simply select a virtual position, and communicate it to all neighbors in the neighbor discovery phase. Nodes then act according to the scheme in [X.Y. Li et al., 2004] using such virtual positions instead of real ones. In addition, we use Delaunay triangulation instead of partial Delauliay triangulation proposed in [X.Y. Li et al., 2004], since each node has all the information needed. Finally, we design experiments to study both the properties of formatted scatternets (such as number of piconets) and the performances of different localized routing methods on them. The experiments confirm good functionality of created Bluetooth networks in addition to their fast creation and straightforward maintenance.

Existing routing and broadcasting protocols for ad hoc networks assume an ideal physical layer model. We apply the log normal shadow fading model to represent a realistic physical layer and propose a MAC layer protocol to produce the optimal shortest hop count routing scheme. We then study the optimal packet forwarding distance to minimize the hop count. A hop count optimal, greedy, localized routing algorithm (referred as ideal hop count routing (IHCR)) is then presented. We also present another algorithm called expected progress routing with acknowledgements (referred as aEPR) and then propose a projection progress scheme. In conclusion, we propose a tR-greedy routing scheme, where the packet is forwarded to the neighbor closest to the destination, among neighbors that are within distance tR. All described schemes are implemented, and their performances are evaluated and compared.

We address the problem of localized scatternet formation for multihop Bluetooth-based personal area ad hoc networks. Nodes are assumed to know their positions and are able to establish connections with any of their neighboring nodes, located within their transmission radius, in the neighbor discovery phase. The next phase of the proposed formation algorithm is optional and can be applied to construct a sparse geometric structure in a localized manner. We propose here a new sparse planar structure, namely, partial Delaunay triangulation (PDT), which can be constructed locally and is denser than other known localized planar structures. In the next mandatory phase, the degree of each node is limited to seven by applying the Yao structure, and the master-slave relations in piconets are formed in created subgraphs. This phase consists of several iterations. In each iteration, undecided nodes with higher keys than any of their undecided neighbors apply the Yao structure to bound the degrees, decide master-slave relations on the remaining edges, and inform all neighbors about either deleting edges or master-slave decisions. To the best of our knowledge, our schemes are the first schemes that construct degree limited (a node has at most seven slaves) and connected piconets in multihop networks, without parking any node. The creation and maintenance require small overhead in addition to maintaining accurate location information for one-hop neighbors. The experiments confirm good functionality of created Bluetooth networks in addition to their fast creation and straightforward maintenance.

The paper by I. Stojmenovic et al. (2002) generated a lot of interest among researchers in ad hoc networks. A number of researchers questioned, through their articles, or directly to the first author, the correctness of the described procedure, and the correctness of the claim that the procedure does not need any communication exchange between nodes, in addition to "hello" messages needed to learn information about neighboring nodes. This correspondence completes the article by providing the actual dominating set definitions used in the procedure (from which zero communication overhead follows easily), the correct procedure (the published one has few misprints at key places), and the proof that the new definitions and procedure indeed define connected dominating sets.

Abstract In a localized routing algorithm, each node currently holding a message makes forwarding decision solely based on the position information about itself, its neighbors and destination. In a unit graph, two nodes can communicate if and only if the distance between them is no more than the transmission radius, which is the same for each node. This paper proposes localized routing algorithms, aimed at minimizing total power for routing a message or maximizing the total number of routing tasks that a network can perform before a partition. The algorithms are combinations of known greedy power and/or cost aware localized routing algorithms and an algorithm that guarantees delivery. A shortcut procedure is introduced in later algorithm to enhance its performance. Another improvement is to restrict the routing to nodes in a dominating set. These improvements require two‐hop knowledge at each node. The efficiency of proposed algorithms is verified experimentally by comparing their power savings, and the number of routing tasks a network can perform before a node loses all its energy, with the corresponding shortest weighted path algorithms and localized algorithms that use fixed transmission power at each node. Significant energy savings are obtained, and feasibility of applying power and cost‐aware localized schemes is demonstrated. Copyright © 2004 John Wiley & Sons, Ltd.

In the minimum energy broadcasting problem, each node can adjust its transmission power in order to minimize total energy consumption but still enable a message originated from a source node to reach all the other nodes in an ad-hoc wireless network. In all existing solutions each node requires global network information (including distances between any two neighboring nodes in the network) in order to decide its own transmission radius. We describe a new localized protocol where each node requires only the knowledge of its distance to all neighboring nodes and distances between its neighboring nodes (or, alternatively, geographic position of itself and its neighboring nodes). In addition to using only local information, our protocol is shown experimentally to be comparable to the best known globalized BIP solution. Our solutions are based on the use of relative neighborhood graph, which preserves connectivity and is defined in localized manner.

A broad variety of location dependent services will become feasible in the near future due to the use of the Global Positioning System (GPS), which provides location information (latitude, longitude and possibly height) and global timing to mobile users. Routing is a problem of sending a message from a source to a destination. Geocasting is a problem of sending a message to all nodes located within a region (e.g. circle or square). Recently, several localized GPS based routing and geocasting protocols for a mobile ad hoc network were reported in literature. In directional (DIR) routing and geocasting methods, node A (the source or intermediate node) transmits a message m to all neighbors located between the two tangents from A to the region that could contain the destination. It was shown that memoryless directional methods might create loops in routing process. In two other proposed methods (proven to be loop-free), geographic distance (GEDIR) or most forward progress within radius (MFR) routing, node A forwards the message to its neighbor who is closest to destination, or has greatest progress towards destination (respectively). In this paper, we propose a general algorithm (based on a unified framework for both routing and geocasting problems), in which message is forwarded to exactly those neighbors, which may be best choices for a possible position of destination (using the appropriate criterion). We then propose and discuss new V-GEDIR and CH-MFR methods and define R-DIR, modified version of existing directional methods. In V-GEDIR method, these neighbors are determined by intersecting the Voronoi diagram of neighbors with the circle (or rectangle) of possible positions of destination, while the portion of the complex hull of neighboring node is analogously used in the CH-MFR method. Routing and geocasting algorithms differ only inside the circle/rectangle. We propose memoryless and past traffic memorization variants of each scheme. The proposed methods may be also used for the destination search phase allowing the application of different routing schemes after the exact destination of position is discovered. Memoryless V-GEDIR and CH-MFR algorithms are loop-free, and have smaller flooding rate (with similar success rate) compared to directional method. Simulations involving the proposed and some known algorithms are in progress and confirm our expectations.

In a multi-hop wireless network, each node is able to send a message to all of its neighbors that are located within its transmission radius. In a flooding task, a source sends the same message to all the network. Routing problem deals with finding a route between a source and a destination. In the activity-scheduling problem, each node decides between active or passive state. We present a scheme whose goal is to prolong network life while preserving connectivity. Each node is either active or has an active neighbor node. Routing and broadcasting are restricted to active nodes that create such dominating set. Activity status is periodically updated during a short transition period. The main contribution of this article is to propose new metrics for previously studied source-independent localized dominating sets, based on combinations of node degrees and remaining energy levels, for deciding activity status.

We introduce the concept of multilinear partition of a point set V/spl sub/R/sup n/ and the concept of multilinear separability of a function f:Vtwo head right arrowK={0,...,k-1}. Based on well-known relationships between linear partitions and minimal pairs, we derive formulae for the number of multilinear partitions of a point set in general position and of the set K(2). The (n,k,s)-perceptrons partition the input space V into s+1 regions with s parallel hyperplanes. We obtain results on the capacity of a single (n,k,s)-perceptron, respectively, for V subset R(n) in general position and for V=K(2). Finally, we describe a fast polynomial-time algorithm for counting the multilinear partitions of K(2).

Geometric, Graph, Combinatorial, and Vector Aspects of Wireless Networks and Mobile Computing'.The main goal was to put together a strong issue emphasizing quality and relevance to current interests in this important field.Wireless communications and mobile computing are redefining computing as a discipline.The impact ranges from medical to military, from industrial to societal.Recently, a number of computer scientists joined the 'hot' field of wireless networks research in order to apply mathematical and algorithmic tools in solving existing problems, and to identify fundamental challenges and future perspectives.The emphasis of this special issue is on applications of design and analysis of algorithms, computational geometry, trigonometry, combinatorial, graph theoretical and vector algebra tools in wireless networks.In response to the Call for Papers, I received 27 submissions from all over the world, leading to a truly international competition.All manuscripts underwent a very rigorous peer review process.On the basis of referee reports, nine papers were selected for inclusion in this special issue.In addition, Xiang-Yang Li was invited to write a survey article on the algorithmic, geometric and graph issues in wireless networks.Selected papers are on various topics of high

Abstract In ad hoc mobile wireless networks, owing to host mobility, broadcasting is expected to be more frequently used to find a route to a particular host, to page a host, and to alarm all hosts. A straightforward broadcasting by flooding is usually very costly and will result in substantial redundancy and more energy consumption. Power consumption is an important issue since most mobile hosts operate on battery. Broadcasting based on a connected dominating set is a promising approach, where only nodes in the dominating set need to relay the broadcast packet. A set is dominating if all the nodes in the system are either in the set or are neighbors of nodes in the set. Wu and Li proposed a simple and efficient distributed algorithm for calculating connected dominating set in ad hoc wireless networks, where connections of nodes are determined by their geographical distances. In general, nodes in the connected dominating set consume more energy to handle various bypass traffic than nodes outside the set. To prolong the life span of each node and, hence, the network by balancing the energy consumption in the system, nodes should be alternately chosen to form a connected dominating set. Activity scheduling deals with the way of rotating the role of each node among a set of given operation modes (e.g. dominating nodes versus dominated nodes). In this paper, we propose to apply the notion of power‐aware connected dominating set to broadcasting and activity scheduling. The effectiveness of the proposed method in prolonging the life span of the network is confirmed through simulation. Copyright © 2003 John Wiley & Sons, Ltd.

Location areas is a popular location management scheme in cellular networks. In the location areas scheme, a mobile terminal updates its location whenever it moves into a cell that belongs to a new location area. However, no matter how the location areas are designed, the location update ping-pong effect exists when a mobile terminal moves back and forth between two location areas. The paper defines a new kind of ping-pong effect, referred to as the generalized ping-pong effect, and shows that it accounts for a non-negligible portion of the total location update cost. Although several strategies have been proposed to reduce the ping-pong effect in the literature, they either fail to eliminate the generalized ping-pong effect or introduce a larger paging cost. The paper proposes a triple-layer location management strategy to eliminate the generalized ping-pong effect, therefore greatly reducing the total location update cost. Simulation results show that the triple-layer strategy outperforms the existing schemes designed to reduce the ping-pong effect.

The up-link bandwidth in satellite networks and in advanced traffic wireless information system is very limited. A server broadcasts data files provided by different independent providers and accessed by many clients in a round-robin manner. The clients who access these files may have different patterns of access. Some clients may wish to access several files in any order (AND), some wish to access one out of several files (OR), and some clients may access a second file only after accessing another file (IMPLY). The goal of the server is to order the files in a way that minimizes the access time of the clients given some a priori knowledge of their access patterns. An appropriate clients-servers model was proposed by Bay-Noy, Naor and Schieber (see Proc. ACM Mobile Computing Conference, MOBICOM 2000, p.222-230, 2000). They formulated three separate problems and proposed an algorithm that evaluates certain number of random permutations and chooses the one whose access time is minimized. We formulate a combined AOI (AND-OR-IMPLY) problem, and propose to apply a parallel hill climbing algorithm (to each of the four problems), which begins from certain number of random permutations, and then applies hill climbing technique an each of them until there is no more improvement. The evaluation time of neighboring permutations generated in hill climbing process is optimized, so that it requires O(n) time per permutation instead of O(n/sup 2/) time required for evaluating access time of a random permutation, where n is the number of files the server broadcasts. Experiments indicate that the parallel hill climbing algorithm is O(n) times faster that random permutations method, both in terms of time needed to evaluate the same number of permutations, and time needed to provide a high quality solution. Thus the improvement is significant for broadcasting a large number of files.

In a localized routing algorithm, each node currently holding message makes routing decision solely based on the information about itself its neighbors and destination. In a unit graph, two nodes can communicate if and only if the distance between them is no more than the transmission radius, which is the same for each node. A localized routing algorithm that guarantees delivery in connected unit graphs has been described previously. Also, several power, cost and power-cost aware metrics and localized loop-free routing algorithms for wireless networks based on the exact power needed for transmission between two nodes, and/or remaining battery power at nodes were proposed. However, these algorithms did not guarantee the delivery of a message in connected unit graphs. This paper proposes such localized routing algorithms, aimed at minimizing total power for routing a message, or maximizing the total number of routing tasks that a network can perform before a partition. The algorithms are combinations of known greedy power and/or cost aware localized routing algorithms and an algorithm that guarantees delivery. A shortcut procedure is introduced in later algorithm to enhance its performance. The efficiency of proposed algorithms is verified experimentally by comparing their power savings, and the number of routing tasks a network can perform before a node loses all its energy, with, the corresponding shortest weighted path algorithms, and localized algorithms that use fixed transmission power at each node. Significant energy savings (which depend mainly on network density and maximum transmission radius) are obtained.

Nodes in a hexagonal network are placed at the vertices of a regular triangular tessellation, so that each node has up to six neighbors. The network is proposed as an alternative interconnection network to a mesh connected computer (with nodes serving as processors) and is used also to model cellular networks where nodes are the base stations. In this paper, we propose a suitable addressing scheme for nodes (with two variants), derive a formula for distance between nodes, and present a very simple and elegant routing algorithm. This addressing scheme and corresponding routing algorithm for hexagonal interconnection are considerably simpler than previously proposed solutions. We then apply the addressing scheme for solving two problems in cellular networks. With the new scheme, the distance between the new and old cell to which a mobile phone user is connected can be easily determined and coded with three integers, one of them being zero. Further, in order to minimize the wireless cost of tracking mobile users, we propose hexagonal cell identification codes containing three, four, or six bits, respectively, to implement a distance based tracking strategy. These schemes do not have errors in determining cell distance in existing hexagonal based cellular networks. Another application is for connection rerouting in cellular networks during a path extension process.

In a multihop wireless network, each node has a transmission radius and is able to send a message to all of its neighbors that are located within the radius. In a broadcasting task, a source node sends the same message to all the nodes in the network. In this paper, we propose to significantly reduce or eliminate the communication overhead of a broadcasting task by applying the concept of localized dominating sets. Their maintenance does not require any communication overhead in addition to maintaining positions of neighboring nodes. Retransmissions by only internal nodes in a dominating set is sufficient for reliable broadcasting. Existing dominating sets are improved by using node degrees instead of their ids as primary keys. We also propose to eliminate neighbors that already received the message and rebroadcast only if the list of neighbors that might need the message is nonempty. A retransmission after negative acknowledgements scheme is also described. The important features of the proposed algorithms are their reliability (reaching all nodes in the absence of message collisions), significant rebroadcast savings, and their localized and parameterless behavior. The reduction in communication overhead for the broadcasting task is measured experimentally. Dominating set based broadcasting, enhanced by a neighbor elimination scheme and highest degree key, provides reliable broadcast with /spl les/53 percent of node retransmissions (on random unit graphs with 100 nodes) for all average degrees d. Critical d is around 4, with <48 percent for /spl les/3, /spl les/40 percent for d/spl ges/10, and /spl les/20 percent for d/spl ges/25. The proposed methods are better than existing ones in all considered aspects: reliability, rebroadcast savings, and maintenance communication overhead. In particular, the cluster structure is inefficient for broadcasting because of considerable communication overhead for maintaining the structure and is also inferior in terms of rebroadcast savings.

Efficient routing among a set of mobile hosts (also called nodes) is one of the most important functions in ad hoc wireless networks. Routing based on a connected dominating set is a promising approach, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. J. Wu and H. Li (1999) proposed a simple and efficient distributed algorithm for calculating connected dominating set in ad hoc wireless networks, where connections of nodes are determined by geographical distances of nodes. In general, nodes in the connected dominating set consume more energy in order to handle various bypass traffics than nodes outside the set. To prolong the life span of each node, and hence, the network by balancing the energy consumption in the network, nodes should be alternated in being chosen to form a connected dominating set. In this paper, we propose a method of calculating power-aware connected dominating set. Our simulation results show that the proposed approach outperforms several existing approaches in terms of life span of the network.

In this paper we propose four schemes that improve the performance of greedy routing method. In the alternate method, the i-th received copy of message m is forwarded to i-th best neighbor, according to the selected criterion (it fails if number of copies exceeds number of neighbors). In the disjoint method, each intermediate node, upon receiving m, will forward it to its best neighbor among those who never received the message (it fails if no such neighbor exists). In the multi-path method, the source node S forwards m to c best neighbors according to distance from D. Each of c created copies afterwards follows the original, alternate, or disjoint method (these copies may interact since copy numbers are not communicated). Component routing method follows original greedy method until a failure node F. Such node F forwards the message to one node (using distance criteria) in each connected component of its neighbors, and then withdraws from the network for that message m (that is, neighboring nodes will ignore F when forwarding further copies of m). Thus F creates c copies of the message, where c is the number of connected components in the subgraph of its neighbors. All proposed methods are loop-free, have improved delivery rate over greedy method and reduced flooding rates compared to other existing methods. Component routing method guarantees delivery of m in connected graphs (even if the location of D is inaccurate).

We consider the problem of synthesizing multiple-valued logic functions by neural networks. A genetic algorithm (GA) which finds the longest strip in V is a subset of K(n) is described. A strip contains points located between two parallel hyperplanes. Repeated application of GA partitions the space V into certain number of strips, each of them corresponding to a hidden unit. We construct two neural networks based on these hidden units and show that they correctly compute the given but arbitrary multiple-valued function. Preliminary experimental results are presented and discussed.

In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer.

A cost aware metric for wireless networks based on remaining battery power at nodes was proposed for shortest-cost routing algorithms, assuming constant transmission power. Power-aware metrics, where transmission power depends on distance between nodes and corresponding shortest power algorithms were also proposed. We define a power-cost metric based on the combination of both node's lifetime and distance-based power metrics. We investigate some properties of power adjusted transmissions and show that, if additional nodes can be placed at desired locations between two nodes at distance d, the transmission power can be made linear in d as opposed to d/sup /spl alpha// dependence for /spl alpha/ /spl ges/ 2. This provides basis for power, cost, and power-cost localized routing algorithms where nodes make routing decisions solely on the basis, of location of their neighbors and destination. The power-aware routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. The cost-aware routing algorithm is aimed at extending the battery's worst-case lifetime at each node. The combined power-cost localized routing algorithm attempts to minimize the total power needed and to avoid nodes with a short battery's remaining lifetime. We prove that the proposed localized power, cost, and power-cost efficient routing algorithms are loop-free and show their efficiency by experiments.

In a localized routing algorithm, node A currently holding the message forwards it based on the location of itself, its neighboring nodes and destination. We propose to use depth first search (DFS) method for routing decisions. Each node A, upon receiving the message for the first time, sorts all its neighbors according to a criteria such as their distance to destination and uses that order in DFS algorithm. It is the first localized algorithm that guarantees delivery for (connected) wireless networks modeled by arbitrary graphs, including inaccurate location information. We then propose the first localized QoS routing algorithm for wireless networks. It performs DFS routing algorithm after edges with insufficient bandwidth or insufficient connection time are deleted from the graph, and attempts to minimize hop count. This is also the first paper to apply GPS in QoS routing decisions, and to consider the connection time (estimated lifetime of a link) as a QoS criterion. The average length of measured QoS path in our experiments, obtained by DFS method, was between 1 and 1.34 times longer than the length of QoS path obtained by shortest path algorithm. The overhead is considerably reduced by applying the concept of internal nodes.

Two metrics where transmission power depends on distance between nodes, and a cost aware metric based on remaining battery power at nodes (assuming constant transmission power), together with corresponding non-localized shortest path routing algorithms, were recently proposed. We define a new power-cost metric based on the combination of both node's lifetime and distance based power metrics. We then propose power, cost, and power-cost GPS based localized routing algorithms, where nodes make routing decisions solely on the basis of location of their neighbors and destination. Power aware localized routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. Cost-aware localized algorithm is aimed at extending battery's worst case lifetime. The combined power-cost algorithm attempts to minimize the total power needed and to avoid nodes with short remaining lifetime. We prove that these localized power, cost, and power-cost efficient routing algorithms are loop-free.

BSR (Broadcasting with Selective Reduction) is a PRAM more powerful than any CRCW PRAM. In order to extend the Broadcast Instruction of BSR and make it more useful for a large class of applications, this article permits it to use a general form of selection, specifically, an arbitrary relational expression. BSR with general selection is denoted by BSR/sup +/. Thus, BSR or BSR with k criteria (k>1) is BSR/sup +/ in a special case. An efficient implementation for the Broadcast Instruction of BSR/sup +/ is proposed, requiring (1/k)th of the circuits used by the best previous implementation of BSR with k criteria. Of all PRAMs, BSR/sup +/ is the most powerful in computation.

The honeycomb mesh, based on hexagonal plane tessellation, is considered as a multiprocessor interconnection network. A honeycomb mesh network with n nodes has degree 3 and diameter /spl ap/1.63/spl radic/n-1, which is 25 percent smaller degree and 18.5 percent smaller diameter than the mesh-connected computer with approximately the same number of nodes. Vertex and edge symmetric honeycomb torus network is obtained by adding wraparound edges to the honeycomb mesh. The network cost, defined as the product of degree and diameter, is better for honeycomb networks than for the two other families based on square (mesh-connected computers and tori) and triangular (hexagonal meshes and tori) tessellations. A convenient addressing scheme for nodes is introduced which provides simple computation of shortest paths and the diameter. Simple and optimal (in the number of required communication steps) routing, broadcasting, and semigroup computation algorithms are developed. The average distance in honeycomb torus with n nodes is proved to be approximately 0.54/spl radic/n. In addition to honeycomb meshes bounded by a regular hexagon, we consider also honeycomb networks with rhombus and rectangle as the bounding polygons.

Recently Akl et al. introduced a new model of parallel computation, called BSR (broadcasting with selective reduction) and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix and other problems. In this paper, we describe constant time solutions to the parenthesis matching, decoding binary trees in bitstring representation, generating next tree shape in B-order, and the reconstruction of binary trees from their traversals, using the BSR model. They are the first constant time solutions to mentioned problems on any model of computation. The number of processors used is equal to the input size, for each problem. A new algorithm for sorting integers is also presented.

The main contribution of this work is to show that a number of digital geometry problems can be solved elegantly on meshes with multiple broadcasting by using a time-optimal solution to the leftmost one problem as a basic subroutine. Consider a binary image pretiled onto a mesh with multiple broadcasting of size [Formula: see text] one pixel per processor. Our first contribution is to prove an Ω(n1/6) time lower bound for the problem of deciding whether the image contains at least one black pixel. We then obtain time lower bounds for many other digital geometry problems by reducing this fundamental problem to all the other problems of interest. Specifically, the problems that we address are: detecting whether an image contains at least one black pixel, computing the convex hull of the image, computing the diameter of an image, deciding whether a set of digital points is a digital line, computing the minimum distance between two images, deciding whether two images are linearly separable, computing the perimeter, area and width of a given image. Our second contribution is to show that the time lower bounds obtained are tight by exhibiting simple O(n1/6) time algorithms for these problems. As previously mentioned, an interesting feature of these algorithms is that they use, directly or indirectly, an algorithm for the leftmost one problem recently developed by one of the authors.

Given a collection of objects in the plane along with a viewpoint /spl omega/, the visibility problem involves determining the portion of each object that is visible to an observer positioned at /spl omega/. The visibility problem is central to various application areas including computer graphics, image processing, VLSI design, and robot navigation, among many others. The main contribution of this work is to provide time-optimal solutions to this problem for several classes of objects, namely ordered line segments, disks, and iso-oriented rectangles in the plane. In addition, our visibility algorithm for line segments is at the heart of time-optimal solutions for determining, for each element in a given sequence of real numbers, the position of the nearest larger element within that sequence, triangulating a set of points in the plane, determining the visibility pairs among a set of vertical line segments, and constructing the dominance and visibility graphs of a set of iso-oriented rectangles in the plane. All the algorithms in this paper involve an input of size n and run in O(log n) time on a mesh with multiple broadcasting of size n/spl times/n. This is the first instance of time-optimal solutions for these problems on this architecture.>

The compaction step of integrated circuit design motivates the study of various visibility problems among vertical segments in the plane. One popular variant is referred to as the Vertical Segment Visibility problem (VSV, for short) and is stated as follows. Given a collection S of n disjoint vertical line segments in the plane, for every endpoint of a segment in S determine the first line segment, if any, interacted by a horizontal ray to the right (resp. left) originating from that endpoint. The contribution of this paper is to propose a time-optimal algorithm for the VSP problem on meshes with multiple broadcasting. The authors then use this algorithm to derive time-optimal solutions for two related problems. All the algorithms run in O(log n) time on a mesh with multiple broadcasting of size n /spl times/ n. This is the first instance of time-optimal solutions for these problems known to us.>

Abstract The star and pancake networks were recently proposed as attractive alternatives to the hypercube topology for interconnecting processors in a parallel computer. However, few parallel algorithms are known for these networks. In this paper, we present several data communication schemes and basic algorithms for these two networks. These algorithms are then used to develop parallel solutions to various computational geometric problems on both networks. Computational geometry is just one area where the algorithms proposed here can be applied. Indeed, we believe that these algorithms are interesting and important in their own right and are fundamental to the design of solutions on the star and pancake networks to a host of other problems. © 1993 by John Wiley & Sons, Inc.

Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family.In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family.In particular, we give O(n log n) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments.We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices.In general, finding a line transversal for a family of n objects takes fl(n log n) time.This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.

An iterative algorithm for generating all partitions of the set {1,…,n} is presented. An empirical test shows that the new algorithm is faster than the previously fastest algorithm recently proposed by Er on some computers, though the former is slower than the latter on a computer where fast recursive call is provided based on an RISC architecture.

On the basis of a backtrack procedure for lexicographic enumeration of all subsets of a set of n elements, we give an algorithm both for determining all bases consisting of functions from a given complete set in a considered subset of the set of k-valued logical functions, and for enumeration of all classes of bases in the subset. We use the lexicographic algorithm also for solving knapsack and minimal covering problems. A cut technique is described which is used in these algorithms to reduce the number of examined subsets of {1, …, n}.