Rate-lifetime tradeoff for reliable communication in wireless sensor networks

The network lifetime and application performance are two fundamental, yet conflicting, design objectives in wireless sensor networks. There is an intrinsic tradeoff between network lifetime maximization and application performance maximization, the latter being often correlated to the rate at which the application can send its data reliably in sensor networks. In this paper we study this tradeoff by investigating the interactions between the network lifetime maximization problem and the rate allocation problem with a reliable data delivery requirement. Severe bias on the allocated rates of some sensor nodes may exist if only the total throughput of the sensor network is maximized, hence we enforce fairness on source rates of sensor nodes by invoking the network utility maximization (NUM) framework. To guarantee reliable communication, we adopt the hop-by-hop retransmission scheme. We formulate the network lifetime maximization and fair rate allocation both as constrained maximization problems. We characterize the tradeoff between them, give the optimality condition, and derive a partially distributed algorithm to solve the problem. Furthermore, we propose an approximation of the tradeoff problem using NUM framework, and derive a fully distributed algorithm to solve the problem.     

Jointly optimal congestion control, channel allocation and power control in multi-channel wireless multihop networks

In this paper, to increase end-to-end throughput and energy efficiency of the multi-channel wireless multihop networks, a framework of jointly optimize congestion control in the transport layer, channel allocation in the data link layer and power control in the physical layer is proposed. It models the network by a generalized network utility maximization (NUM) problem with elastic link data rate constraints. Through binary linearization and log-transformation, and after relaxing the binary constraints on channel allocation matrix, the NUM problem becomes a convex optimization problem, which can be solved by the gateway centralized through branch and bound algorithm with exponential time complexity. Then, a partially distributed near-optimal jointly congestion control, channel allocation and power control (DCCCAPC) algorithm based on Lagrangian dual decomposition technique is proposed. Performance is assessed through simulations in terms of network utility, energy efficiency and fairness index. Convergence of both centralized and distributed algorithms is proved through theoretic analysis and simulations. As the available network resources increase, the performance gain on network utility increases.     

A high performance optimal dynamic routing algorithm with unicast multichannel QoS guarantee in communication systems

Dynamic routing protocols play an important role in today??s networks. In communication networks, in a current data transmission session, failing nodes and links is a destructor event which loses packets immediately and it can also waste network resources and services seriously. Sometimes failing nodes can disconnect data transmission and, therefore, lost packets must be retransmitted by new session. In this situation, the routing algorithm must discard failed nodes and must repair paths of session by rerouting them. In this case, static routing algorithms and some existing dynamic routing algorithms cannot manage faulty paths fairly and network efficiency is seriously declined. The capability to compensate for topology changes is the most important advantage dynamic routing offers over static routing. An efficient dynamic routing algorithm tries to reroute and change faulty paths without disconnecting sessions and keeps packet transmission in a desirable rate. It is important to tell that a dynamic routing algorithm should provide multi essential parameters, such as acceptable delay, jitter, bandwidth, multichannel paths, virtual channel connections, label switching technology, optimal resource allocation, optimal efficiency in the case of multimedia, and real time applications. This paper proposes a new dynamic framework which transforms static routing algorithms to dynamic routing algorithms. Using the new dynamic framework, this paper constructs an Optimal Dynamic Unicast Multichannel QoS Routing (ODUMR) algorithm based on the Constrained Based Routing (CBR) and Label Switching Technology which is called as ODUMR Algorithm. The performance of ODUMR is analyzed by network simulator tools such as OpNet, MATLAB, and WinQSB. ODUMR produces results better than the existing static and dynamic routing algorithms in terms of necessary parameters.     

Alternative Distributed Algorithms for Network Utility Maximization: Framework and Applications

Network utility maximization (NUM) problem formulations provide an important approach to conduct network resource allocation and to view layering as optimization decomposition. In the existing literature, distributed implementations are typically achieved by means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements that, thus far, have not been fully exploited, such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents a systematic framework to exploit alternative decomposition structures as a way to obtain different distributed algorithms, each with a different tradeoff among convergence speed, message passing amount and asymmetry, and distributed computation architecture. Several specific applications are considered to illustrate the proposed framework, including resource-constrained and direct-control rate allocation, and rate allocation among QoS classes with multipath routing. For each of these applications, the associated generalized NUM formulation is first presented, followed by the development of novel alternative decompositions and numerical experiments on the resulting new distributed algorithms. A systematic enumeration and comparison of alternative vertical decompositions in the future will help complete a mathematical theory of network architectures.     

Autonomous and adaptive resource allocation among multiple nodes and multiple applications in heterogeneous wireless networks

In the forthcoming future, various means of wireless communication, such as cellular, Wi-Fi, WiMAX, and DSRC, will be available to mobile users and applications. With the development of wireless communication and mobile devices, more and more users and applications will be accommodated in mobile environment. Since mobile users and applications compete for the limited wireless resources whose communication quality dynamically change, we need an adaptive mechanism for mobile users and applications to share the available network resources while satisfying each application?s QoS requirements. In this paper, we propose an adaptive resource allocation mechanism where each node autonomously determines wireless network resources to assign to each of networked applications running on it. For this purpose, we adopt an attractor composition model, which is based on an autonomous and adaptive behavior of biological systems. Through numerical analysis, we confirmed that our mechanism could adaptively and stably allocate wireless network resources to applications, while considering their QoS requirements and fairly sharing network resources with other nodes. It also is shown that our mechanism superiors to a mechanism where a node determines resource allocation by solving an optimization problem.     

State-centric programming for sensor-actuator network systems

Distributed embedded systems such as wireless sensor and actuator networks require new programming models and software tools to support the rapid design and prototyping of sensing and control applications. Unlike centralized platforms and Web-based distributed systems, these distributed sensor-actuator network (DSAN) systems are characterized by a massive number of potentially failing nodes, limited energy and bandwidth resources, and the need to rapidly respond to sensor input. We describe a state-centric, agent-based design methodology to mediate between a system developer's mental model of physical phenomena and the distributed execution of DSAN applications. Building on the ideas of data-centric networking, sensor databases, and proximity-based group formation, we introduce the notion of collaboration groups, which abstracts common patterns in application-specific communication and resource allocation. Using a distributed tracking application with sensor networks, we'll demonstrate how state-centric programming can raise the abstraction level for application developers.     

Stability of primal–dual gradient dynamics and applications to network optimization

This paper considers dynamic laws that seek a saddle point of a function of two vector variables, by moving each in the direction of the corresponding partial gradient. This method has old roots in the classical work of Arrow, Hurwicz and Uzawa on convex optimization, and has seen renewed interest with its recent application to resource allocation in communication networks. This paper brings other tools to bear on this problem, in particular Krasovskii’s method to find Lyapunov functions, and recently obtained extensions of the LaSalle invariance principle for hybrid systems. These methods are used to obtain stability proofs of these primal–dual laws in different scenarios, and applications to cross-layer network optimization are exhibited.     

Fog computing for next-generation Internet of Things: Fundamental,state-of-the-art and research challenges

In recent times, the Internet of Things (IoT) applications, including smart transportation, smart healthcare, smart grid, smart city, etc. generate a large volume of real-time data for decision making. In the past decades, real-time sensory data have been offloaded to centralized cloud servers for data analysis through a reliable communication channel. However, due to the long communication distance between end-users and centralized cloud servers, the chances of increasing network congestion, data loss, latency, and energy consumption are getting significantly higher. To address the challenges mentioned above, fog computing emerges in a distributed environment that extends the computation and storage facilities at the edge of the network. Compared to centralized cloud infrastructure, a distributed fog framework can support delay-sensitive IoT applications with minimum latency and energy consumption while analyzing the data using a set of resource-constraint fog/edge devices. Thus our survey covers the layered IoT architecture, evaluation metrics, and applications aspects of fog computing and its progress in the last four years. Furthermore, the layered architecture of the standard fog framework and different state-of-the-art techniques for utilizing computing resources of fog networks have been covered in this study. Moreover, we included an IoT use case scenario to demonstrate the fog data offloading and resource provisioning example in heterogeneous vehicular fog networks. Finally, we examine various challenges and potential solutions to establish interoperable communication and computation for next-generation IoT applications in fog networks.     

Cross-layer optimization for wireless multihop multicast networks

Cyber-Physical System (CPS) is envisioned to tightly integrate the cyber-world of computation, communication, and control with the physical world. CPS is typically designed as a networked system of interacting sensors, actuators, and embedded computing devices to monitor and control the physical world. Thus, one of the essential building blocks of such a system is a highly efficient networking infrastructure. In this paper, we aims to develop an efficient wireless networking technology which can be utilized in CPS. More specifically, we develop a cross-layer optimization model based on the Network Utility Maximization (NUM) framework and its distributed solution for wireless multihop multicast networks exploiting multi-user diversity. It is known that the capacity of a wireless network can be increased by exploiting different channel conditions at different users, i.e., multi-user diversity; however, it is yet to be determined how much performance gain can be achieved by exploiting multi-user diversity in wireless multihop multicast networks. To address this problem, we extend the NUM framework and derive a new optimization problem including the benefits of multi-user diversity for multicasting scenarios in wireless multihop networks under a probabilistic media access control (MAC). In our problem, multi-user diversity is achieved via opportunistic scheduling. Then, we propose a distributed approximation algorithm for the problem. Our numerical results confirm that the benefit of multi-user diversity is prominent in a wireless multihop network with multicast flows.     

Decentralized management of bi-modal network resources in a distributed stream processing platform

This paper presents resource management techniques for allocating communication and computational resources in a distributed stream processing platform. The platform is designed to exploit the synergy of two classes of network connections—dedicated and opportunistic. Previous studies we conducted have demonstrated the benefits of such bi-modal resource organization that combines small pools of dedicated computers with a very large pool of opportunistic computing capacities of idle computers to serve high throughput computing applications. This paper extends the idea of bi-modal resource organization into the management of communication resources. Since distributed stream processing applications demand large volume of data transmission between processing sites at a consistent rate, adequate control over the network resources is important to ensure a steady flow of processing. The system model used in this paper is a platform where stream processing servers at distributed sites are interconnected with a combination of dedicated and opportunistic communication links. Two pertinent resource allocation problems are analyzed in detail and solved using decentralized algorithms. One is mapping of the processing and the communication tasks of the stream processing workload on the processing and the communication resources of the platform. The other is the dynamic re-allocation of the communication links due to variations in the capacity of the opportunistic communication links. Overall optimization goal of the allocations is higher task throughput and better utilization of the expensive dedicated links without deviating much from the timely completion of the tasks. The algorithms are evaluated through extensive simulation with a model based on realistic observations. The results demonstrate that the algorithms are able to exploit the synergy of bi-modal communication links towards achieving the optimization goals.     

CA-DAG: Modeling Communication-Aware Applications for Scheduling in Cloud Computing

This paper addresses performance issues of resource allocation in cloud computing. We review requirements of different cloud applications and identify the need of considering communication processes explicitly and equally to the computing tasks. Following this observation, we propose a new communication-aware model of cloud computing applications, called CA-DAG. This model is based on Directed Acyclic Graphs that in addition to computing vertices include separate vertices to represent communications. Such a representation allows making separate resource allocation decisions: assigning processors to handle computing jobs, and network resources for information transmissions. The proposed CA-DAG model creates space for optimization of a number of existing solutions to resource allocation and for developing novel scheduling schemes of improved efficiency.     

A Rate Allocation Framework for Multi-Class Services in Software-Defined Networks

Software defined networking (SDN) is a network architecture with a programmable control plane (e.g., controllers) and simple data plane (e.g., forwarders). One of the popular SDN protocols/standards is OpenFlow, for which researchers have recently proposed some quality-of-service (QoS) supports. However, the proposals for rate allocation have some limitations in network scalability and multi-class services’ supports. In the literature, rate allocation formulations are commonly based on the framework of network utility maximization (NUM). Nevertheless, multi-class services are rarely considered in that framework since they make the formulated NUM become nonconvex and prevent its subgradient-based algorithm from converging. In this paper, we propose a scalable QoS rate allocation framework for OpenFlow in which multi-class services are considered. The convergence issue in the algorithm of our NUM-based framework is resolved by an admission control scheme. The network scalability is improved by our decentralized algorithms that can run on multiple parallel controllers. Extensive simulation and emulation results are provided to evaluate the performance of our method.     

基于DQN的超密集网络能效资源管理

小基站的密集随机部署会产生严重干扰和较高能耗问题,为降低网络干扰、保证用户网络服务质量（QoS）并提高网络能效,构建一种基于深度强化学习（DRL）的资源分配和功率控制联合优化框架。综合考虑超密集异构网络中的同层干扰和跨层干扰,提出对频谱与功率资源联合控制能效以及用户QoS的联合优化问题。针对该联合优化问题的NP-Hard特性,提出基于DRL框架的资源分配和功率控制联合优化算法,并定义联合频谱和功率分配的状态、动作以及回报函数。利用强化学习、在线学习和深度神经网络线下训练对网络资源进行控制,从而找到最佳资源和功率控制策略。仿真结果表明,与枚举算法、Q-学习算法和两阶段算法相比,该算法可在保证用户QoS的同时有效提升网络能效。     

User satisfaction aware routing and energy modeling of polymorphic network on chip architecture

In mobile devices, multiple applications contend for limited resources in the underlying embedded system framework. Application resource requirements in mobile systems vary by computation needs, energy consumption and user interaction frequency. Quality of service (QoS) is the predominant metric of choice to manage resources among contending applications. Resource allocation policies to support static QoS for applications do not reflect the changing demands of the user in contemporary network on chip (NoC) based embedded architectures. User satisfaction with the user interactions and user interface design ought to be the primary design driver. Some recent research has integrated a saturating, non-linear user satisfaction function in the application thread scheduler. The application and operating system level user satisfaction research assumes that the throughput of inter-thread edges is limited only by the computational constraints of the nodes. With NoC, however, NoC resource allocation policies play an important role in determining the inter-thread communication flow’s throughput and the resulting application level user satisfaction. In this paper, we filter down the user satisfaction from an application layer attribute to a router level attribute to improve the resource and energy utilization for routing in order to leverage the user satisfaction at the application and system level. We demonstrate that this technique improves the user satisfaction of audio (MP3) application by 10% while maintaining the user satisfaction of video (MPEG-2) application. Experiments also show that a fixed energy source can be extended for an average of 18% of the time using the NoC user satisfaction based energy optimization proposed in this research.     

A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation

Multiagent resource allocation provides mechanisms to allocate bundles of resources to agents, where resources are assumed to be indivisible and nonshareable. A central goal is to maximize social welfare of such allocations, which can be measured in terms of the sum of utilities realized by the agents (utilitarian social welfare), in terms of their minimum (egalitarian social welfare), and in terms of their product (Nash product social welfare). Unfortunately, social welfare optimization is a computationally intractable task in many settings. We survey recent approximability and inapproximability results on social welfare optimization in multiagent resource allocation, focusing on the two most central representation forms for utility functions of agents, the bundle form and the k-additive form. In addition, we provide some new (in)approximability results on maximizing egalitarian social welfare and social welfare with respect to the Nash product when restricted to certain special cases.     

Resource allocation decisions under various demands and cost requirements in an unreliable flow network

This paper considers resource allocation decisions in an unreliable multi-source multi-sink flow network, which applies to many real-world systems such as electric and power systems, telecommunications, and transportation systems. Due to uncertainties of components in such an unreliable flow network, transmitting resources successfully and economically through the unreliable flow network is of concern to resource allocation decisions at resource-supplying (source) nodes. We study the resource allocation decisions in an unreliable flow network for a range of demand configurations constrained by demand-dependent and demand-independent cost considerations under the reliability optimization objective. Solutions to these problems can be obtained by computing the resource allocation for each demand configuration independently. In contrast, we pursue an updating scheme that eludes time-consuming enumeration of flow patterns, which is necessary in independent computation of resource allocations for different demand configurations. We show that updating is attainable under both demand-independent and demand-dependent cost constraints when demand incurs an incremental change, and demonstrate the proposed updating scheme with numerical examples.     

Overlay network resource allocation using a decentralized market-based approach

We present a decentralized market-based approach to resource allocation in a heterogeneous overlay network. This resource allocation strategy dynamically assigns resources in an overlay network to requests for service based on current system utilization, thus enabling the system to accommodate fluctuating demand for its resources. Our approach is based on a mathematical model of this resource allocation environment that treats the allocation of system resources as a constrained optimization problem. From the solution to the dual of this optimization problem, we derive a simple decentralized algorithm that is extremely efficient. Our results show the near optimality of the proposed approach through extensive simulation of this overlay network environment. The simulation study utilizes components taken from a real-world middleware application environment and clearly demonstrates the practicality of the approach in a realistic setting.     

An adaptive multi-path computation framework for centrally controlled networks

The Adaptive Dynamic Multi-Path Computation Framework (ADMPCF) is to provide an integrated resource control and management platform with an adequate set of management applications for better routing and resource allocation in centrally controlled or loosely coupled distributed software defined networking (SDN), especially for large network systems. As an open and extensible solution framework, it can provide the necessary infrastructure and integrates data collection and analytics, network performance evaluation, and various optimization algorithms. ADMPCF utilizes a set of complementary algorithms that work together in an adaptive and intelligent fashion that enable global routing and resource allocation optimization. It can also be easily extended to incorporate new algorithms through some open APIs. Such an approach would be able to efficiently and effectively adapt to the rapid changes in network topology, states, and most importantly application traffic, while it is often infeasible for a single optimization algorithm to get satisfactory solution for multiple nonlinear optimization objectives and constraints for a large and centrally controlled network. As it would be costly for centrally controlled global optimization algorithms to calculate good routes dynamically with adequate response time, the proposed ADMPCF framework takes advantage of many hidden patterns of the network information fragments in the combinations of network topology, states, and traffic flows. Therefore, it can lead to a much improved data structure for fast search and match that avoids the expensive re-optimization whenever possible.     

mReno: a practical multipath congestion control for communication networks

In current networks, end-user devices are usually equipped with several network interfaces. The design of a multipath protocol that can cooperate with current single-path transport protocols is an interesting research field. Most previous works on multipath network utility maximization (NUM) lead to rate-based control protocols. Moreover, these studies do not model a case in which paths from a source may have different characteristics. Thus, these approaches are difficult to deploy to the Internet. In this paper, we introduce a multipath NUM model for a network with both multipath and single-path users. The proposed algorithm converges to a global solution to the multipath NUM. Based on the mathematical framework, we develop a multipath TCP called mReno. Analysis and simulations indicate that mReno is completely compatible with TCP Reno and achieves load-balance, fairness, and performance improvement targets.