A library of static and dynamic communication algorithms for parallel computation

Communication efficiency is one of the keys to the broad success of parallel computation, as one can see by looking at the successes of parallel computation, which are currently limited to applications that have small communication requirements, or applications that use a small number of processors. In order to use fine grain parallel computation for a broader range of applications, efficient algorithms to execute the underlying interprocessor communications have to be developed. In this paper we survey several generic static and dynamic communication problems that are important for parallel computation, and present some general methodologies for addressing these problems. Our objective is to obtain a collection of communication algorithms to execute certain prototype communication tasks that arise often in applications. These algorithms can be called as communication primitives by the programmer or the compiler of a multiprocessor computer, in the same way that subroutines implementing standard functions are called from a library of functions in a conventional computer. We discuss both algorithms to execute static (deterministic) primitive communication tasks, as well as schemes that are appropriate for dynamic (stochastic) environments. Our emphasis is on algorithms that apply to many similar problems and can be used in various network topologies. This revised version was published online in June 2006 with corrections to the Cover Date.     

Joint Task Migration and Power Management in Wireless Computing

We investigate a wireless computing architecture, where mobile terminals can execute their computation tasks either 1) locally, at the terminal's processor, or 2) remotely, assisted by the network infrastructure, or even 3) combining the former two options. Remote execution involves: 1) sending the task to a computation server via the wireless network, 2) executing the task at the server, and 3) downloading the results of the computation back to the terminal. Hence, it results to energy savings at the terminal (sparing its processor from computations) and execution speed gains due to (typically) faster server processor(s), as well as overheads due to the terminal server wireless communication. The net gains (or losses) are contingent on network connectivity and server load. These may vary in time, depending on user mobility, network, and server congestion (due to the concurrent sessions/connections from other terminals). In local execution, the wireless terminal faces the dilemma of power managing the processor, trading-off fast execution versus low energy consumption. We model the system within a Markovian dynamic control framework, allowing the computation of optimal execution policies. We study the associated energy versus delay trade-off and assess the performance gains attained in various test cases in comparison to conventional benchmark policies.     

Three-Phase Algorithms for Task Scheduling in Distributed Mobile DSP System with Lifetime Constraints

A distributed mobile DSP system consists of a group of mobile devices with different computing powers. These devices are connected by a wireless network. Parallel processing in the distributed mobile DSP system can provide high computing performance. Due to the fact that most of the mobile devices are battery based, the lifetime of mobile DSP system depends on both the battery behavior and the energy consumption characteristics of tasks. In this paper, we present a systematic system model for task scheduling in mobile DSP system equipped with Dynamic Voltage Scaling (DVS) processors and energy harvesting techniques. We propose the three-phase algorithms to obtain task schedules with shorter total execution time while satisfying the system lifetime constraints. The simulations with randomly generated Directed Acyclic Graphs (DAG) show that our proposed algorithms generate the optimal schedules that can satisfy lifetime constraints.     

Cross-Layer Collaborative In-Network Processing in Multihop Wireless Sensor Networks

Emerging wireless sensor network (WSN) applications demand considerable computation capacity for in-network processing. To achieve the required processing capacity, cross-layer collaborative in-network processing among sensors emerges as a promising solution: sensors do not only process information at the application layer, but also synchronize their communication activities to exchange partially processed data for parallel processing. However, scheduling computation and communication events is a challenging problem in WSNs due to limited resource availability and shared communication medium. In this work, an application-independent task mapping and scheduling solution in multihop homogeneous WSNs, multihop task mapping and scheduling (MTMS), is presented that provides real-time guarantees. Using our proposed application model, the multihop channel model, and the communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously. The dynamic voltage scaling (DVS) algorithm is presented to further optimize energy consumption. Simulation results show significant performance improvements compared with existing mechanisms in terms of minimizing energy consumption subject to delay constraints     

Dynamic Task-Based Anycasting in Mobile Ad Hoc Networks

Mobile ad hoc networks (MANETs) have received significant attention in the recent past owing to the proliferation in the numbers of tetherless portable devices, and rapid growth in popularity of wireless networking. Most of the MANET research community has remained focused on developing lower layer mechanisms such as channel access and routing for making MANETs operational. However, little focus has been applied on higher layer issues, such as application modeling in dynamic MANET environments. In this paper, we present a novel distributed application framework based on task graphs that enables a large class of resource discovery based applications on MANETs. A distributed application is represented as a complex task comprised of smaller sub-tasks that need to be performed on different classes of computing devices with specialized roles. Execution of a particular task on a MANET involves several logical patterns of data flow between classes of such specialized devices. These data flow patterns induce dependencies between the different classes of devices that need to cooperate to execute the application. Such dependencies yield a task graph (TG) representation of the application.We focus on the problem of executing distributed tasks on a MANET by means of dynamic selection of specific devices that are needed to complete the tasks. In this paper, we present simple and efficient algorithms for dynamic discovery and selection (instantiation) of suitable devices in a MANET from among a number of them providing the same functionality. This is carried out with respect to the proposed task graph representation of the application, and we call this process Dynamic Task-Based Anycasting. Our algorithm periodically monitors the logical associations between the selected devices, and in the event of a disruption in the application owing to failures in any component in the network, it adapts to the situation and dynamically rediscovers the affected parts of the task graph, if possible. We propose metrics for evaluating the performance of these algorithms and report simulation results for a variety of application scenarios differing in complexity, traffic, and device mobility patterns. From our simulation studies, we observed that our protocol was able to instantiate and re-instantiate TG nodes quickly and yielded high effective throughput at low to medium degrees of mobility and not much below 70% effective throughput for high mobility scenarios.     

Analysis and modeling of task scheduling in wireless sensor network based on divisible load theory

In this paper, we propose a novel task scheduling algorithm (Divisible Task scheduling Algorithm for Wireless sensor networks (DTAW)) based on divisible load theory in heterogeneous wireless sensor networks to complete the tasks within the shortest possible time and reduce the sensors' energy‐consuming. In DTAW, the tasks are distributed to the wireless sensor network by the (SINK) on the basis of the processing and communication capacity of each sensor. After receiving the subtasks, the intracluster sensors carry out its tasks simultaneously and send the results to cluster head sequentially. By removing communication interference between each sensor, reduced task completion time and improved network resource utilization are achieved. Each cluster head simultaneously finishes sending fused data to the SINK after fusing the data obtained from intracluster sensors. In this way, the overlap between the task performing and communication phase would be much better. Simulation results are presented to demonstrate the impacts of different network parameters on the makespan and energy consumption. The results show that the algorithm enables to reasonably distribute tasks to each sensor and then effectively reduces the time‐consuming and energy‐consuming. Copyright © 2012 John Wiley & Sons, Ltd.     

Energy-Scalable Protocols for Battery-Operated MicroSensor Networks

In wireless sensor networks, the goal is to gather information from a large number of sensor nodes and communicate the information to the end-user, all under the constraint of limited energy resources. Network protocols minimize energy by using localized communication and control and by exploiting computation/communication tradeoffs. In addition, data fusion algorithms such as beamforming aggregate data from multiple sources to reduce data redundancy and enhance signal-to-noise ratios, thus further reducing the required communications. We have developed a sensor network system that uses a localized clustering protocol and beamforming data fusion to enable energy-efficient collaboration. We compare the performance of two beamforming algorithms, the Maximum Power and the Least Mean Squares (LMS) beamforming algorithms, using the StrongARM SA-1100 processor. Results show that the LMS algorithm requires less than one-fifth the energy required by the Maximum Power beamforming algorithm with only a 3 dB loss in performance, thus showing that the LMS algorithm is better suited for energy-constrained systems. We explore the energy-scalability of the LMS algorithm, and we propose an energy-quality scalable architecture that incorporates techniques such as variable filter length, variable voltage supply and variable adaptation time.     

Wireless cars: A cyber-physical approach to vehicle dynamics control

A non-conventional drive-by-wireless technology for guidance and control of a redundantly actuated electric car supported by an on-board wireless network of sensors, actuators and control units is proposed in this article. Several optimization-based distributed feedforward control schemes are developed for such powertrain infrastructures. In view of the limitations of the commercial off-the-shelf wireless communication technologies and the harshness of the in-vehicle environments, a pressing design and implementation aspect, in addition to the robustness against information loss, refers to fulfilling the hard real-time computational requirements. In this work, we address such problems by introducing several distributed event-based control schemes in conjunction with adaptive scheduling at the protocol level. Hereby we obtain a simple tuning mechanism to compromise between the outcome accuracy and computation efficiency (i.e., communication traffic intensity). Using simulative evaluations, we demonstrate the viability of the proposed algorithms and illustrate the impact of external interferences in an IEEE 802.15.4 based wireless communication solution.     

A Trusted Waterfall Framework Based Peer to Peer Protocol for Reliable and Energy Efficient Data Transmission in MANETs

Advances in lattice-based cryptography are enabling the use of public key algorithms (PKAs) in power-constrained ad hoc and sensor network devices. Unfortunately, while many wireless networks are dominated by group communications, PKAs are inherently unicast—i.e., public/private key pairs are generated by data destinations. To fully realize public key cryptography in these networks, lightweight PKAs should be augmented with energy efficient mechanisms for group key agreement. Recently, many key management schemes for the WSNs have been proposed, but the computation and communication costs of these protocols are too high to suitable for WSNs. This paper proposes a key establish protocol for the WSNs based on combined key. The protocol adopts seed key mapping technology to achieve two-party and multi-party key establish in the WSNs, it can generate a large number of combination keys with little resources. So it effectively solve the contradiction between the sensor nodes need large storage space to store shared key with their neighbors and their limited storage space. It can also achieve mutual authentication between nodes when they establish shared key. Analysis shows that the proposed protocol has the advantages in storage efficiency, computation consumption and Communication consumption and suitable for wireless networks.     

Fuzzy logic–based distributed clustering protocol to improve energy efficiency and stability of wireless smart sensor networks for farmland monitoring systems

Wireless smart sensor networks (WSSNs) are emerging as the physical backbone of the internet of things (IoT) technology. On the basis of the IoT platform, web‐based systems and services are been developing such as e‐surveillance, industrial‐IoT, and precision agriculture. For farmland monitoring systems, WSSNs need to be scalable in terms of coverage area. Sensor nodes are energy‐constrained devices, and hence, many energy‐efficient clustering protocols are developed in the literature. But these methods overload the cluster leaders (CLs) with cluster computation and data communication costs. An improper CL selection may lead to the early death of such nodes and hence does not prolong the network lifetime stability. We propose a fuzzy logic (FL)–based distributed clustering protocol to enhance the energy efficiency of WSSN while maximizing the coverage area. The load of CLs is shared by originators and super‐CLs (SCLs) selected in the network. The wireless link and received signal strength (RSS) are greatly affected by environmental conditions and thus cannot be considered as ideal network parameters. We use FL systems to tackle the uncertainty of such network parameters. The proposed protocol is simulated for different scalable WSSNs. The results indicate that the proposed protocol provides better lifetime stability than the recent conventional protocols. The functionalities of the protocol are proposed considering the recent wireless standards. Hence, the proposed protocol can be suitably implemented for farmland monitoring systems.     

Energy-aware on-demand scatternet formation and routing for Bluetooth-based wireless sensor networks

Bluetooth is a promising short-range wireless communication technology with the characteristics of interference resilience and power efficiency, both desirable for wireless sensor networks. The new Intel Mote sensor devices have Bluetooth technology incorporated as the standard wireless communications interface. When using Bluetooth in applications where multihop routing is required, groups of Bluetooth piconets combine together to form a scatternet. However, most of the existing scatternet formation protocols are designed to facilitate communications between any two pairs of devices, regardless of the actual traffic demand pattern. For wireless sensor network applications with low-duty-cycle traffic patterns, an on-demand scatternet formation protocol can achieve significant power saving by avoiding unnecessary network connectivity. To that end, we introduce an on-demand scatternet and route formation protocol designed specifically for Bluetooth-based wireless sensor networks. Our protocol builds a scatternet on demand, and is able to cope with multiple sources initiating traffic simultaneously. In addition, our energy-aware forwarding nodes selection scheme is based on local information only, and results in more uniform network resource utilization and improved network lifetime. Simulation results show that our protocol can provide scatternet formation with reasonable delay and good load balance, which results in prolonged network lifetime for Bluetooth-based wireless sensor networks.     

DDPG-based intelligent rechargeable fog computation offloading for IoT

In view of the existing computation offloading research on fog computing network scenarios, most scenarios focus on reducing energy consumption and delay and lack the joint consideration of smart device rechargeability. This paper proposes a deep deterministic policy gradient-based intelligent rechargeable fog computation offloading mechanism that is combined with simultaneous wireless information and power transfer technology. Specifically, an optimization problem that minimizes the total energy consumption for completing all tasks in a multiuser scenario is formulated, and the joint optimization of the task offloading ratio, uplink channel bandwidth, power split ratio and computing resource allocation is fully considered. Based on the above nonconvex optimization problem with a continuous action space, a communication, computation and energy harvesting co-aware intelligent computation offloading algorithm is developed. It can achieve the optimal energy consumption and delay, and similar to a double deep Q-network, an inverting gradient updating-based dual actor-critic neural network design can improve the convergence and stability of the training process. Finally, the simulation results validate that the proposed mechanism can converge quickly and can effectively reduce the energy consumption with the lowest task delay.

     

Distributed Kalman Filter with Fast Consensus for Wireless Sensor Networks

With the revolution of wireless sensor networks and the advances on microchip technologies the potential of distributed interconnected systems have exploded. Yet, even with great sensing capability and great communication throughput in the wireless links, we encounter fundamental problems: Communication Congestion and Scalability. The scalability issue and communication congestion are closely related in the application of distributed estimation algorithms. The more sensors we add to our system the more communication we will require. In general, in order to share the information gathered by all the sensors, we also get a higher likelihood of running into critical network congestion. Moreover, the scalability problem is not only related to communication issues but also to computation problems, as with higher dimensional measurement vectors it also comes a higher computational demand for the estimation algorithms. Distributed Kalman Filter (DKF) is one of the most fundamental distributed estimation algorithms. Most of the proposed DKF in the literature rely on consensus filters algorithm. The convergence rate of such distributed consensus algorithms typically depends on the network topology and the weights given to the edges between neighboring sensors. This paper proposes a DKF with fast consensus. The idea is to apply a polynomial filter on the network matrix in order to increase the convergence by minimizing its second largest eigenvalue of the polynomial. Fast convergence can contribute to significant energy saving. Moreover we redesigned the DKF to reduce its computational complexity and to reduce the communication traffic between the sensor nodes. Thus, the experimental results show that the TelosB mote can run DKF with up to seven neighbors for real application.     

Life of birds [wireless sensor network for bird study]

This paper presents a wireless sensor network being used for the study of Leach's storm petrel on Great Duck Island, Maine, USA. The petrel-watching apparatus consists of a distributed system of devices called 'motes', each having the dual functions of data collection and communication. For the former role, the mote contains application-specific sensors and signal-processing hardware; for the latter, the mote has a low-power radio transceiver. When the motes are networked together, each simultaneously collects data from its immediate surroundings and passes its own and other motes' data through the network.     

Mathematical Evaluation of Environmental Monitoring Estimation Error through Energy-Efficient Wireless Sensor Networks

In this paper, the estimation of a scalar field over a bidimensional scenario (e.g., the atmospheric pressure in a wide area) through a self-organizing wireless sensor network (WSN) with energy constraints is investigated. The sensor devices (denoted as nodes) are randomly distributed; they transmit samples to a supervisor by using a clustered network. This paper provides a mathematical framework to analyze the interdependent aspects of WSN communication protocol and signal processing design. Channel modelling and connectivity issues, multiple access control and routing, and the role of distributed digital signal processing (DDSP) techniques are accounted for. The possibility that nodes perform DDSP is studied through a distributed compression technique based on signal resampling. The DDSP impact on network energy efficiency is compared through a novel mathematical approach to the case where the processing is performed entirely by the supervisor. The trade-off between energy conservation (i.e., network lifetime) and estimation error is discussed and a design criterion is proposed as well. Comparison to simulation outcomes validates the model. As an example result, the required node density is found as a trade-off between estimation quality and network lifetime for different system parameters and scalar field characteristics. It is shown that both the DDSP technique and the MAC protocol choice have a relevant impact on the performance of a WSN.     

低WSN服务能耗的MAC协议实现

为解决WSN服务能耗和服务质量问题,提出了一种无线传感器网络介质访问控制协议WTRP-S,分析比较了WTRP-S,WTRP和IEEE802.15.4MAC的性能,建立了节点启动调度模型。仿真结果表明:在数据业务大的网络中,该协议既能保证服务质量,在节点关闭通信模块中能够节省更多能量,使得整体能耗降低,WTRP-S适用于能量受限的无线传感器网络。     

Scate: A Scalable Time and Energy Aware Actor Task Allocation Algorithm in Wireless Sensor and Actor Networks

In many applications of wireless sensor actor networks (WSANs) that often run in harsh environments, the reduction of completion times of tasks is highly desired. We present a new time‐aware, energy‐aware, and starvation‐free algorithm called Scate for assigning tasks to actors while satisfying the scalability and distribution requirements of WSANs with semi‐automated architecture. The proposed algorithm allows concurrent executions of any mix of small and large tasks and yet prevents probable starvation of tasks. To achieve this, it estimates the completion times of tasks on each available actor and then takes the remaining energies and the current workloads of these actors into account during task assignment to actors. The results of our experiments with a prototyped implementation of Scate show longer network lifetime, shorter makespan of resulting schedules, and more balanced loads on actors compared to when one of the three well‐known task‐scheduling algorithms, namely, the max‐min, min‐min, and opportunistic load balancing algorithms, is used.     

Topology estimation method for telecommunication networks

In order to resolve the traditional limited lifetime problem, energy harvesting technology has been introduced into wireless sensor network (WSN) in recent years, engendering a new kind of network which is called energy harvesting wireless sensor network (EHWSN). In EHWSNs, besides the traditional issues, such as energy consumption, energy equilibrium, transmission efficiency, etc., there are still new challenges, such as how to utilize harvested energy efficiently and how to make more sensor nodes so as to achieve unlimited lifetime under actual situation. In this paper, inspired by slime mold Physarum polycephalum, a novel bionic routing protocol, abbreviated as EHPRP, is proposed for EHWSNs to address above problems without predicting harvestable energy value. Three distributed routing algorithms with low algorithm complexity are proposed which would prominently reduce the processing delay and conserve energy. Furthermore, the mathematic theoretical analysis is made to prove the stability of EHPRP routing strategy. Finally, simulation results present that, compared with other typical algorithms, EHPRP consumes less energy, always making the whole network obtain an unlimited lifetime, and displaying more uniform network energy distribution under different workload conditions.     

Augmentation of spectral efficiency in optical wireless communication networks using grid-based elephant swarm optimization protocol

The emergence of 5G and 6G technologies has resulted in a faster, more automated, and more intelligent data flow in the digital world. A wide spectrum of optical wireless communication is made available to support 5G and 6G technologies, and it can meet the demands of high-speed optical wireless communication. Trade-offs involving latency, power consumption, deployment costs, and hardware/computational overhead have always been a part of 5G/6G technologies. The decline in the trade-offs indicated above has major implications for networking capacity. The proposed work modulated a new grid-based communication protocol (GCP) with elephant swarm optimization (ESO) to surpass those issues with optical wireless communication devices. This protocol employs an integrated strategy to split the network and choose the cluster head effectively. Different GCP-ESO-related algorithms have been explored. Various components of the OSNs, including network energy usage, cluster, and non-cluster header nodes, are also calculated using mathematical analysis. The results have been simulated using MATLAB software. The simulation precisely demonstrates that the proposed GCP-ESO outperforms the emerging MCH-EOR and RDSAOA-EECP methods concerning energy consumption (0.46 J), packet loss ratio (PLR) (0.60%), end-to-end latency (11.0 s), packet delivery rate (PDR) (99.41%), routing (0.112), the lifetime of the network (3718 s), and throughput (0.989 Mbps).     

Minimisation de la consommation d’Énergie dans les réseaux ad hoc

An ad hoc network is a collection of wireless devices forming a temporary network independently of any administration or fixed infrastructure. The main benefits of this new generation of mobile networks are flexibility and their low cost. Wireless devices have maximum utility when they can be used “anywhere at anytime “. However, one of the greatest limitations to that goal is the finite power supplies. Since batteries provide limited power, a general constraint of wireless communication is the short continuous operation time of mobile terminals. This constraint is more important for the ad hoc networks, since every terminal has to perform the functions of a router. Therefore, energy consumption should be a crucial issue while designing new communication protocols and particularly ad hoc routing protocols. We propose, in this paper, some extensions to the most important on-demand routing algorithm,Aodv (Ad hoc On demand Distance Vector). The discovery mechanism in these extensions uses energy as a routing metric. These algorithms improve the network survivability by maintaining the network connectivity, which is the strong requirement for a high-quality communication. They carry out this objective with low message overhead for computing routes and without affecting the other network protocol layers.