Minimum-Resource Multicast Communications 

Get Complete Project Material File(s) Now! »

Chapter 2 Minimum-Resource Multicast Communications

Introduction

Recently, CR has been considered as the radio platform for multi-hop ad hoc networks (see, e.g. [19, 41]). An important service that must be supported by ad hoc networks is multicast. Al-though there is an abundance of research on multicast in ad hoc networks (see Section 2.2), those results cannot be applied to a CR ad hoc network, due to the complexity associated with a CR node (e.g., multiple available frequency bands, difference in available bands from neighboring nodes). In addition, a single-layer approach (e.g., multicast routing [37]) is overly simplistic when resource optimization (i.e., minimizing network resource) is also an objective, in addition to multicast con-nectivity. In this context, a cross-layer approach is usually necessary, which should include joint consideration of multiple lower layers, in addition to network layer. However, such joint formula-tion is usually highly complex and difficult, as we shall soon see in this chapter (Section 2.4).
It is important to contrast a CR ad hoc network to a closely related network – MC-MR network [1, 25, 26]. First, MC-MR employs traditional hardware-based radio technology and thus each radio can only operate on a single channel at a time and there is no switching of channel on a per-packet basis. Thus, the number of concurrent channels that can be used at a wireless node is limited by the number of radios. In contrast, the radio technology in CR is software-based; a soft radio is capable of switching frequency bands on a per-packet basis. As a result, the number of concurrent frequency bands that can be used by CR is typically much larger than that can be supported by MC-MR. Second, a common assumption for MC-MR is that there is a set of common channels available for every node in the network. Such assumption is hardly true for a CR networks (CRN), in which each node may have a different set of available frequency bands (those bands not used by primary users). An even more profound advance in CR technology is that future CR can work on non-contiguous channels for transmission/reception. These important differences between MC-MR and CR warrant that the algorithm design for a CR ad hoc network is substantially more complex than that for a MC-MR network. In some sense, a MC-MR network can be considered as a special case of a CRN. Thus, algorithms designed for a CR ad hoc network can be extended to address a MC-MR network while the converse is not true.
In this chapter, we consider a multi-hop CR ad hoc network and study how to minimize network-wide resource requirement to support a set of multicast communication sessions. In this network, the available frequency bands at each node may be different and two neighboring nodes can communicate with each other only if they share at least one common band. For each multicast session, there is a source node and a group of destination nodes. Further, there is a flow bit rate that must be transported from the source node to its group of destination nodes. To minimize required network resource (measured in network-wide bandwidth-footprint product (BFP)) to support these multicast communication sessions, we find that it is necessa ry to follow a cross-layer approach, with joint formulation of frequency band scheduling and multicast routing. Through mathematical modeling, we formulate the optimization problem as a mixed-integer linear programming (MILP).
In this chapter, we give the development of a polynomial-time algorithm to the cross-layer optimization problem (MILP) that offers a highly competitive solution. We observe that although there are many integer variables in the problem formulation, the binary scheduling variable (for band assignment on each link) is the core variable and its determination will help determine other integer variables. Based on this observation, we focus on fix ing these scheduling variables through an iterative process via a relaxed linear program (LP) of the original problem. Further, during each iteration, we take an explicit topological consideration during the fixing of these scheduling variables and follow a “bottom-up” approach (from leaf to ro ot) for multicast tree construction. At the end of the last iteration, all these integer variables will be fixed and the values for the other variables can be obtained by solving a LP.
To measure the performance of our proposed solution, we compare it to a lower bound obtained via an optimization solver (CPLEX). Note that the optimal solution (unknown) is between the solution obtained by our algorithm and the lower bound by CPLEX. Simulation results show that the solution obtained by our algorithm is very close to the lower bound, thus suggesting that the solution by our algorithm is even closer to the optimum.
The remainder of this chapter is organized as follows. Section 2.2 reviews related work. In Section 2.3, we study the characteristics associated with multicast communications in a CR ad hoc network, thus laying the ground for mathematical modeling. In Section 2.4, we present mathemat-ical model for our problem. In Section 2.5, we present the solution to our optimization problem. Section 2.6 presents simulation results and demonstrates its near-optimal performance. Section 2.7 concludes this chapter.

Related Work

In this section, we review related work on multicast in multi-hop ad hoc networks. We organize this section as follows. First, we examine prior efforts on multicast for ad hoc networks with each node equipped with single traditional radio. Then we review related work on multicast for MC-MR ad hoc networks. To the best of our best knowledge, there is so far no result for multicast problem for a multi-hop CR ad hoc network.
There has been a large body of work on multicast for ad hoc network with each node equipped with a single hardware-based (traditional) radio, e.g., [2, 6, 8, 11–13, 18, 27, 28, 34, 48–51]. Among nthese works, the focus in [6, 8, 48–51], was on energy-efficie nt multicast routing, while the focus in [11–13, 18, 34], was on lifetime-optimal multicast, eith er with directional antennas or omni-directional antennas. In [2,27,28], the authors studied multicast throughput maximization problem.
In the context of MC-MR network, multicast was studied in [33,53]. In [33], the authors studied channel assignment for multicast problem in MC-MR wireless mesh networks. Here, the authors first assumed that there is a pre-built multicast tree (e.g., via multicast ad-hoc on-demand distance vector (MAODV) protocol). Then they proposed a channel assignment algorithm which greedily assigns a channel to each transmitting node so as to minimize the interference among nodes in the multicast tree. In [53], Zeng et al. studied a joint routing and channel assignment problem for MC-MR wireless mesh networks with the goal of maximizing throughput. The authors proposed layer-by-layer decoupled heuristic algorithm called multi-channel multicast (MCM). The MCM algorithm builds a multicast tree via two steps. First, it uses a breadth-first-search (BFS)-based algorithm to obtain level information for each node; then it constructs a tree from the lowest level and follows a greedy algorithm in selecting parent nodes. Once the multicast tree is obtained, the channel assignment part commences, where authors proposed two algorithms, depending on whether the channels are orthogonal or overlapping.

Understanding Multicast Problem in a CRN

In this section, we explore some characteristics associated with the multicast problem in a CRN. Such characteristics are not only important to help us understand the underlying difficulties in this problem, but also set the stage for our mathematical modeling and problem formulation in Section 2.4.
Before we describe each characteristic in detail, let us recall the general setting for an ad hoc CRN under investigation. The network that we consider in this chapter is an ad hoc network with each node equipped with a CR. There is a set of available frequency bands for communication at each node, depending on its location. Such bands may include those bands that are currently not in-use by primary users. Given the differences in geographical location, the set of available frequency bands at one node may be different from those at another node in the network. This is also a unique feature that distinguishes an ad hoc CRN from a conventional MC-MR network.
We organize this section as follows. From Section 2.3.1 to 2.3.5, we discuss some unique and interesting characteristics associated with the multicast problem in a CRN. Section 2.3.6 concludes our discussion with an example illustrating of the multicast problem and potential solution.

Transmission and Interference in a CRN

Under a traditional wireless network, nodes typically share the same pool of frequency bands. Whether two nodes can communicate with each other or not is only limited by the transmission range. But in a CRN, there is an additional constraint that must be considered. That is, we must make sure that there is at least a common band that is available between the two nodes. If no such band is available, then the two nodes will not be able to communicate with each other. Figure 2.1 illustrates this constraint with a two-node example. Here node 1 has a set of available bands {a, b, e} while node 2 has a set of available bands {c, d}. Since there is no common band between the two sets, nodes 1 and 2 cannot communicate with each other.
Under a traditional wireless network, whether a node can interfere another node or not is only determined by the interference range. Again, such interference relationship is based on the as-sumption that all nodes in the network operate on the same frequency band. But for an ad hoc CRN, the interference relationship is much more complicated, due to the potential difference in the set of available frequency bands at different nodes. As an example, Fig. 2.2 shows three pairs of nodes. Node 1 transmits to node 2 on band a while node 3 transmits to node 4 on band b and c.
There is no interference on node 2 (from node 3) due to node 3’s transmission is on different bands. But node 5 is not allowed to transmit to node 6 on band a due to its interference on node 2.

Full Duplex via Different Bands

Under a traditional wireless network, a node typically cannot transmit and receive at the same time, due to half-duplex (self-interference) constraint on the same time. But for an ad hoc CRN, full duplex is possible, if a node transmit and receive on different bands. An example is given in Fig. 2.3, where the available bands at nodes 1, 2, and 3 are {a}, {a, b}, and {b}, respectively. Therefore, the common band between nodes 1 and 2 is band a and that between nodes 2 and 3 is band b. In this case, node 2 can transmit to node 3 on band b while receiving from node 1 on (a) Node 0 uses 4 bands {a, b, c, d} to cover all 5 neighbor- (b) Node 0 uses 2 bands a, e} to cover all 5 neigh-ing nodes. boring nodes.

Multicast Band Scheduling

Under a traditional ad hoc wireless network, a transmission at a node can be heard by all its one-hop neighboring nodes. This is true since all nodes are assumed to operate on the same band. As discussed, this may not be true in an ad hoc CRN as the available bands on each node may be different and two nodes can communicate with each other only if they share a common band. Due to such diversity in available bands between a source node and its one-hop neighboring nodes, it might be necessary to employ multiple bands to achieve one-hop multicast. As an example, in Fig. 2.4, suppose we have a source node 0 with available bands {a, b, c, d, e}, with node 0’s one-hop neighboring nodes being 1, 2, 3, 4, and 5. Suppose the available bands at these five nodes are {a, e}, {a, b}, {b, e}, {c, e}, and {d, e}, respectively. It is not difficult to verify that there does n ot exist one common band that node 0 can use to multicast to all five neighboring nodes. So multipl e bands must be used at node 0 to achieve this purpose.

1 Introduction 
1.1 Background
1.2 Characteristics of CR
1.3 New Technical Challenges
1.4 Problems Considered in This Thesis
1.5 Summary of Contributions
1.6 Thesis Outline
2 Minimum-Resource Multicast Communications 
2.1 Introduction
2.2 Related Work
2.3 Understanding Multicast Problem in a CRN
2.4 Mathematical Modeling
2.5 A Proposed Solution
2.6 Simulation Results
2.7 Conclusion
3 Joint Optimization of MIMO and Cognitive Radio Networks 
3.1 Introduction
3.2 Understanding CRNMIMO
3.3 Mathematical Modeling
3.4 Simulation Results
3.5 Conclusion
4 Summary and Future Work 
4.1 Summary of Contributions
4.2 Future Research Directions
Bibliography
GET THE COMPLETE PROJECT
Some Modeling and Optimization Problems in Cognitive Radio Ad Hoc Networks