بهینه سازی تقاطع-لایه ای برای عملکرد تجارت کردن در شبکه مبتنی بر کد بی سیم شبکه های چند هاپ

Maximizing network lifetime and optimizing aggregate system utility are important but usually conflict goals in wireless multi-hop networks. For the trade-off particularly for such networks equipped with the capability of network coding, we introduce a cross-layer optimization approach that can seamlessly accommodate routing, scheduling and stream control to simultaneously meet the diverse objectives with the aid of network utility maximization. Specifically, by taking into account both intra- and inter-session network coding and cross-layer formalization, the algorithms resulted are considered to be more general than those obtained from, e.g., poison-remedy based methods that focus on the methodology of network coding itself. In particular, along with a Markov Chain Monte Carlo method and a CSMA approximation, these algorithms can dynamically approach the optimal solution while solving the scheduling subproblem involved, which is NP-hard in general, in a distributed manner. Finally, we present numerical results for the insight that can be gained from the cross-layer optimization and show that this work is capable on achieving an optimal trade-off between the lifetime and utility.

Wireless networks with multi-hop transmissions such as wireless sensor networks (WSNs) are usually composed of a large number of stations equipped with batteries of a limited size to perform their tasks of sensing, computing and wireless communication. For applications in such energy-constraint networks, minimizing energy consumption poses a considerable challenge to the engineers, and maximizing network lifetime continuously intensifies the interest of researchers in the development of energy-efficient wireless transmission schemes, leading to various relevant approaches on physical layer [1], MAC layer [2], network layer [3], and even cross-layer [4] and [5]. Apart from the energy issue, the interference-heavy nature of wireless media presents another great challenge for designing high-throughput wireless multi-hop networks. For this challenge, many techniques have been developed; however, these developments usually build around the existing “routing” concept, and if based on a cross-layer design, they are generally focusing on the network utility maximization problem resulted, as those shown, e.g., in [6] and the references therein. Beyond the conventional solutions based on routing, Ahlswede et al. recently introduce in their work [7] that by allowing intermediate nodes to perform coding operations in addition to pure packet forwarding, network coding can achieve the maximum multicast rate and thus can improve the overall network throughput. Following that, Li et al. [8] show that linear network coding would suffice to achieve the maximum rate, and Ho et al. [9] further demonstrate that random linear codes can achieve the linear network code rate asymptotically. Since then, different related problems have been proposed and solved with this technology. For example, the problem of achieving min-cost multicast in networks has been studied [10], and the rate control problem for the multicast flows had been addressed [11], all by means of network coding. With the advent of this technology, network coding can be further classified into two different categories. The first is intra-session network coding, which focuses on a single multicast session and coding is performed on packets from the same session. The second is inter-session network coding, which considers multiple coexisting sessions with their coding performed on packets across different sessions. Among the above, intra-session network coding is more understood since its achievable multicast rate can be characterized by the min-cut max-flow theorem [7]. Specifically, this flow-based characterization can lead to an extension of the cross-layer optimization framework in wireless networks, which will be shown in the first part of this work. On the other hand, its counterpart, inter-session network coding, is very difficult and so far only few methods can find non-trivial solution to this problem [12]. Among these few works, opportunistic XOR coding had been proposed in [13] that uses simple one-hop nature, and constructive XOR coding across pairs of unicast sessions was considered in [14]. In addition, an inter-session network coding strategy has been proposed in [15] to carry out opportunistic unicast with XOR inter-session coding under primal-interference model and maximal scheduling, which could lead to a fraction of maximum utility. Referring to the XOR-based approach in above as immediately decodable network coding (IDNC), a more recent work [16] develops its IDNC schemes to control packet transmissions for the unicast sessions subject to hard deadline constraints. Specifically, by paying attention to the decoding delay that may be introduced by NC, this work proposes its solution for the scenario where a base station conducts two unicast sessions of packets with deadline constraints to be received by their two different destinations in time. Subject to similar hard deadline constraints on the packets transmitted to N instead of only two receivers, an adaptive NC scheme is proposed in [17] that sequentially adjusts the coding block length of NC to maximize the system throughput. By comparing the above two works with ours, it could be seen that these works focus on the deadlines on their session packets broadcasted from one transmitter to two or more receivers in single-hop networks whereas our work aims to the maximization and tradeoff of lifetime and system utility subject to intra- and inter-session NC schemes in multi-hop networks. Note also that although a finite-energy system with NC can be designed to maximize the system utility before the energy is depleted for further transmission, energy (or lifetime) constraint and delay constraint could not be used interchangeably in our work, unlike that noted in [17]. This is because we actually consider the initial energy in each node and the energy consumption of each hyperlink to estimate how long a node would be alive or workable, and hence the lifetime is not directly related to the coding delay in our case. More specifically, for the inter-session network coding, in the second part of this paper we will adopt a similar XOR coding approach but apply it under general interference model and distributed back-pressure scheduling, which can further achieve utility optimality asymptotically. Inspired by the previous works [9], [12], [18] and [19], this approach will consider one-hop coding opportunity where a coded packet would be decoded at the immediate next-hop node, and uses session decomposition method to search the local butterfly structures [15]. With these features, this approach could be regarded as a generalization of XOR poison-remedy flow scheme [20] and COPE scheme [13]. To address the various issues, cross-layer optimization recently attracts more attention in the society because it can coordinate resources allocated to different layers to achieve globally optimal performance. In particular, network utility maximization (NUM) could be a key tool mainly considered for this aim. Although primal-based and dual-based algorithms are all possible for NUM on the optimization, related works [21] and [22] more usually focus on dual-based algorithms that can decompose a problem with Lagrange approaches and obtain the relevant subgradients to conduct their distributed algorithms. As a complement of the above, some recent works [18], [19], [23] and [24] further consider primal–dual based algorithms along with Markov approximations to result in a smoother trajectory than that of dual algorithms. Following this methodology, in [25] we introduce a joint optimization model for wireless networks in convention, which did not consider network coding; further in [26], we give a cross-layer optimization framework for network lifetime maximization, which, however, only considered intra-session network coding and did not involve multiple objectives and their trade-off. In this work, we propose a novel approach for joint network lifetime and utility optimization particularly tailored for wireless multi-hop networks equipped with different capabilities of network coding, and develop its objectives and cross-layer constraints for the performance trade-off, implemented in a distributed manner, which are different from those of related works based on a similar ground. To summarize, we characterize the cross-layer optimization as follows: • Unlike the conventional optimization approaches, e.g., [27], [28], [29], [30], [31] and [25], with or without considering multiple objectives, while all of them paying no attention to network coding, our work readily contributes on a cross-layer optimization formulation that can account for a wireless network equipped with the different capabilities of network coding. • When compared with the related works based on network coding, e.g., [32], [12], [33], [18] and [26], which usually consider conventional optimization schemes focusing on a single objective in the coded networks, our work explicitly dedicates to a cross-layer optimization framework with various cross-layer constraints that can lead to an optimal trade-off between the diverse objectives of network lifetime and throughput utility, in a distributed manner. In the remaining of this paper, we first introduce our cross-layer non-linear programming model in Section 2. Then, to solve the joint optimization problem, we propose stochastic primal–dual distributed algorithms in Section 3. Following that, the distributed optimization for intra-session network coding and that for inter-session network coding are introduced in Sections 4 and 5, respectively. These online dynamic algorithms are then numerically examined in Section 6. Finally, conclusions are drawn in Section 7.

With network coding, we have introduced in this work a mathematical framework for the joint lifetime and rate utility maximization that can be implemented in a distributed manner by means of primal–dual control algorithm, back-pressure scheduling algorithm, log-sum-exp approximation, Markov Chain Monte Carlo method, and network coding method, which cooperatively constitute the primal–dual subgradient distributed algorithms under consideration. Specifically, with the distributed algorithms proposed, each node can independently operate on a CSMA-based protocol to dynamically approximate the optimal system performance, without pre-specified set of routes and scheduling parameters, and solves the key problem of scheduling in wireless ad hoc networks. The experiment results readily show that the cross-layer optimization is capable on achieving the joint objective by using the distributed computations, and contributed valuable viewpoints on the optimization framework with respect to the network coding schemes adopted. Given the basis of this work, we will aim to solve the challengeable problem of adding a new model to incorporate inter-session network coding instead of the existing one shown in this work, which will be our future work of the first priority.