Research Article
Multi-Video-Sources Selection Strategy in Mobile P2P Streaming Media Architecture
College of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou, Zhejiang, 310018, People’s Republic of China
With the rapid improvement of the performance of mobile telephone, people have already looked on it not only as a personal information processing platform but also as an important entertainment platform. When they are in the journey or idle, people have been accustomed to get and watch the interested video by the mobile telephone or the other mobile device. In P2P (Peer to Peer) network, the communication between the peers need not depend on a DNS(Domain Name Server) and a server and peers can directly exchange data each other. The distributed architecture makes the P2P system robust and the characteristic of P2P network makes it be suitable to the mobile network applications. As the mobile techniques and P2P network rapidly develop, the wide application prospect of mobile P2P streaming media system can be predicted.
In mobile P2P streaming media system, because the upload bandwidths of the service peers were limited, the receiver peers often needed to request the data from multi-video-sources. Nguyen and Zakhor (2002) showed the feasibility and benefits of streaming from multiple servers to a single receiver in the distributed video streaming framework. At the same time, they proposed a rate allocation algorithm to determine the sending rate of each server to minimize the total packet loss. The rating assignment problem for multi-version streams was studied by Liu et al. (2006) and they computed an optimal streaming rate for each stream version. Similar to Liu et al. (2006), Hsu and Hafeeda (2007a) and Magharei and Rejaie (2006) employed layered-scalable coding to adapt to the heterogeneous bandwidth. The multi-sender streaming problem was formulated to maximize the streaming quality of all peers and minimize the load on the originating media distributor (Hsu and Hafeeda, 2007b). Magharei and Rejaie (2006) designed a practical algorithm to adapt to bandwidth dynamics. However, they only considered coarse-grained scalability and are not R-D optimized. Su and Wang (2006) considered a minimization problem for the transmission of FGS-coded images. They formulated the problem as a nonlinear programming problem and transformed it to a series of Linear Programming (LP) sub-problems, where each sub-problem determined a peer allocation to maximize the number of received bits in a given time bound. However, they didnt consider the characteristic of R-D models. Hsu anf Hafeeda (2007a) considered the relationship between coding efficiency of FGS and served-custom range. After, they traded off the coding efficiency of FGS and served-custom range, they proposed an algorithm to determine the best base layer bit rate of single or multiple video streams. However, their optimized object is video source end instead of video client end. The bit distribution problem at different aggregation levels for FGS-encoded sequences was studied. De Cuetos et al. (2005) formulated a minimization problem for the total distortion for a block of frames of different sequences and solved it using dynamic programming method. They had validated frame aggregations reduced the complexity of dynamic programming method without compromising the quality. But the algorithm required each sender had a complete video stream. Nemati et al. (2008) proposed a multi-source streaming model for mobile peer-to-peer (P2P) overlay network and they scheduled the multi-source by serial way.
In mobile P2P streaming media system, there often exists multiple video sources. This study is to solve the serial and parallel scheduling problem for multiple video sources and the bit assignment problem of stream.
THE VIDEO STREAMING ARCHITECTURE BASED ON MOBILE P2P NETWORK
An architecture of a mobile P2P network employs the framework of the super-unstructured P2P architecture. The framework divides all peers into two or several layers by their comprehensive capacity. The peers with strong power become super-peers and the other peers become leaf peers. Each leaf peer is connected to an adjacent super-peer and each super-peer connects some leaf peers and some other super-peers. The information of shared files is only saved in super-peers. This architecture integrates several merits, such as high efficiency of centralized search, autonomy, load balance and robustness of decentralized search. At the same time, it trades off the centralized structure and the decentralized structure and makes full use of the difference of peers capacity. However, unlike to the cable network, the mobile P2P architecture cannot directly employ the present P2P architecture. The operation of a mobile network is controlled by its operation business and the network model for P2P application must be controllable. Hence, based on the super unstructured P2P network, all peers in the architecture are factitiously classified into two categories: General Super-Peers (GSP) and the Special Super-Peers (SSP) controlled by the mobile-network operator. A general fixed peer is connected to a GSP and a mobile device is connected to SSP. Consequently, the original super-unstructured P2P architecture need almost not be changed and only some peers controlled by the mobile-network operator join the system and become super-peers. The original fixed peers are not affected. Figure 1 shows the mobile P2P architecture.
Because the present mobile network employs layered structure, pure P2P networks dont exist and the datum can not be directly shared between peers. Hence, some independent mobile agent servers are introduced and all mobile devices finish dual connection by it. Figure 2 shows the architecture with agent servers.
Fig. 1: | The general mobile P2P architecture |
Fig. 2: | The mobile P2P architecture with agent servers connecting some mobile devices |
In this architecture, a group of mobile devices are connected to an agent server and the identifier of each mobile node is announced in the mobile P2P network such that each mobile device can independently work by an agent server. In fact, a super-peer controlled by mobile-network operator can be viewed as an independent mobile P2P agent server, which can capture all functions of an agent sever. In the mobile P2P video streaming system, the bandwidth and operation power of mobile devices are limited. Hence, in the architecture, the multiple video sources must be correctly scheduled in order to improve the bandwidth utilization ratio of the receiving peer, video perceived quality and meet the real-time requirement.
THE FRAMEWORK OF THE ALGORITHM
Figure 3 shows the framework of this algorithm. A peer firstly submits the streaming media service search request to the connected superpeers and superpeers find the service peer set which satisfies the expected Qos by the common resource search algorithms. If the service peer set isnt empty, the multiple video sources are scheduled by a serial strategy and the different video sources are synchronized by the time model of a streaming.
Fig. 3: | The framework of this algorithm |
If the service peer set is empty, it is proved that there no any service peer can alone provide the expected Qos. The superpeers start to find the service peer set which possesses the requested media content and the expected Qos is satisfied by parallel way in which multiple video sources concurrently serve a receiving peer. In parallel method, the frame bit assignment algorithm is presented to maximize the perceived quality. If the receiving peer has moved, it just reconnects a new superpeer and repeats the above process. Next, the serial and parallel scheduling methods are described in detail.
THE SERIAL SCHEDULING ALGORITHM FOR MULTIPLE VIDEO SOURCES
If the service peer set which satisfies the expected Qos isnt empty, let SP indicate the service peer set and let Pr indicate the current requesting peer. Because SP is not empty, there are some service peers which each of can provide the expected Qos and multiple vide sources are scheduled by serial way. Firstly, Pr randomly chooses a service peer from this set to request stream data and monitors the Qos provided by this service peer in real time. If the Qos is degraded for the moving of this service peers, communication congestion or declining in service capacity, Pr re-chooses a service peer from this set to request stream data. Because a different service peer may have a different stream version, such as a different resolution and a frame rate, multiple video sources must be synchronized to play seamlessly video in client end when a service peer is switched.
The synchronization method between multiple video sources: In fact, a video streaming just is a bit sequence. If two service peers have the same streaming version, the same bit sequence is transmitted and vice versa. As a result, a service peer is switched to another service peer which possesses the different stream version, the multiple video sources must be synchronized. Let BSi indicate the bit sequence sent by the service peer SPi, let |BSi| indicate the length of BSi, let BTi indicate the time length to play BSi and let |BSi| indicate the sub-sequence of Bsi which is between the time t1 and the time t2. Obviously, the average bit rate Bri = |BSi|/BTi. Suppose the service peer Pi starts to send the stream data to Pr at time t0 and another service peer Pj takes over the service peer Pi at time t1 because the Qos of Pi is degraded and the subsequence sent by Pi is . For the same time, another service peer Pk takes over the service peer Pj at time t2 and the subsequence sent by Pj can be marked as and so on. Figure 4 shows the process. Obviously, when Pi, Pj and Pk have different stream version, the time variable t records the length of the sent subsequence and multiple video sources can be effectively synchronized by it. When a service peer is switched, one just passes the time parameter t to the new service peer and let the new service begin to send the stream data at time t. At the same time, in order to ensure that Pr can play seamlessly the received video, let each service peer transmit some margins of stream data to consider the synchronization delay. As shown in Fig. 4, the length of time in which Pi sends the stream data is δ longer than t1-t0 and the start time at which Pj starts to send the stream data is δ earlier than the time t1.
Fig. 4: | The synchronization theory of multiple video sources |
THE PARALLEL SCHEDULI- NG ALGORITHM FOR MULTIPLE VIDEO SOURCES
If the service peer set is empty, it is proved that there no any service peer can alone provide the expected Qos. The superpeers start to find the service peer set which possesses the required media content and the expected Qos is satisfied by parallel way in which multiple video sources concurrently serve a receiving peer. Because each video source has a different part of a sequence and different upload bandwidth, the receiving peer must properly choose video sources and reasonably allocation limited download bandwidth to maximize perceived quality. This algorithm assumes the bit rate of base layer of FGS-encoded video sequence is low and can be reliably transmitted to the receiving peer. The parallel scheduling algorithm mainly optimizes and reasonably allocates the bit stream of the enhancement layers of FGS-encoded video sequence, because its bit rate is high and controllable. Because a video sequence is composed of lots of frames, a parallel scheduling problem for multiple video sources can be transformed into receiving-peer-driven frame-level bit allocation problem. In another word, a parallel scheduling algorithm is to allocation the transmission task of each frame to each video source such that the perceived quality of a receiving peer is maximized.
The model of the bit allocation problem: For ease of exposition, let T indicate a frame period, which is fixed in a sequence; let n indicate the number of video sources; let bwi(iε[1, n]) indicate the bandwidth of the video sources i (these information can be collected by peer exchange or the other protocols); let ei indicate the number of successive bits of the enhancement layer possessed by video source i and without loss of generality, let e1≤e2≤ en; let R indicate the bandwidth of receiver; let Δi indicate the number of bits which are allocated to video source i and let ri indicate the bit rates which are allocated to video source i. And, then the optimized problem can be formalized into selecting the optimal Δi(iε[1, n]) and ri(iε[1, n]) to maximize the perceived quality. If the perceived quality is represented by the distortion and D(r) is denoted as the R-D function, then the bit allocation problem can be modeled as:
(1) | |
and Δi, ri ε N; I = 1,2, ,n.
where, Δi-riT≤0 ensures that the number of bits which are allocated to the video source i is less than its transmission capacity;
ensures that the number of bits which are allocated to the video source i is within the portion of bits saved by the video source i; ri≤bwi ensures that the bit rate which is allocated to the video source i is less than its upload bandwidth and
ensures that the sum of received bit rate is less than its download bandwidth. As shown in Eq. 1, this problem is a non-linear programming problem (NLP) which is a NP-complete. Assume Δi comes from j different bit-planes and segt (tε[1, j]) represents the number of bits of the bit plane t and then
where, j is a variable. Therefore, the Eq. 1 can be transformed into the Eq. 2.
(2) |
Equation. 1 and 2 indicate the choice and design of R-D function D(r) are very important to simplify the problem. Hsu and Hefeeda (2008) has shown the piece linear R-D model is accurate and low time complexity. What is more important is the property of the piece linear R-D model is helpful to the design of the optimizing algorithm. Hence, the algorithm employs the piece linear R-D model as D(r). Based on the piece linear R-D model and unwrapped Eq. 2, all items which belong to the same bit-plane are merged into a new item denoted as bpv(vε[1, z]), where, bpv is the number of transmitted bits from the bit-plane v and z is the total number of bit-planes of the considered frame. Let gv is the slope of the bit-plane v and then the bit allocation problem can be further converted to:
(3) |
and Δi ri, bpvεN; i = 1,2, ,n; v = 1,2, ,z.
where, lv(v = 1,2, ,z) is the size of the bit plane v; d is the distortion when only the base layer is transmitted; the new constraint condition bpv≤lv ensures the number of allocated bits is less than the size of the bitplane v;
ensures that the total number of bits transmitted from different bitplanes is exactly the same as the number of bits allocated to the video sources. As shown in the Eq. 3, the original NLP problem is transformed into an Integer Linear Programming (ILP) problem. However, it is still a NP-complete. Δi ri, bpvεN; i = 1,2, ,n; v = 1,2, ,z is relaxed to Δi ri, bpvε ; i = 1,2, ,n; v = 1,2, ,z, such that the ILP problem can be transformed into a general Linear Programming (LP) problem, which is easily solved with the simplex method or the other existing method.
The solutions of the LP problem and the (ILP) problem are approximately mapped by a simple method. Assume that:
is the optimal solution of LP problem, where, indicate some non-negative real number and then the solution of ILP can be gotten by the followed piecewise function.
(4) |
Obviously, all constrain conditions except for Δi-riT≤0 can be naturally satisfied and the Δi-riT≤0 is ensured by the piecewise function 4. Where, is rounded down and the maximum error is not more than one. For, when
it is directly rounded to an integer and the maximum error is not more than one. As a result, the cumulative error is not more than n and the cumulative error is not more than nT+n in other two cases. Obviously, the approximate solution of ILP gotten by the piecewise function is close to his optimal solution. A greedy strategy is employed in the design and implement on the ILP to accelerate the algorithm. The basic idea of greedy strategy is to maximize the number of bytes sent by each video source and to make full use of the download bandwidth of the receiving peer.
THE EXPERIMENT RESULTS
All algorithms proposed in this study have been implemented and validated. Because the serial scheduling algorithm for multiple video sources is relatively simple, the experiment results shown here are only for the parallel scheduling algorithm. From lots of video sequences, four typical test sequences are chose such as coastguard, flower, foreman and mobile. Several experiment cases are also constructed and the Table 1 summarizes these cases. In Table 1, the incoming bandwidth of 1, 2, 4 and 100 M simulates the present popular internet and intranet streaming setting. The third column in the Table 1 enumerates the setting of all video sources and in the numeric pairs, the former is outgoing bandwidth of the video source and the latter is the bit stream version.
Figure 5 and 6 show the experiment results. In figures, the vertical axis is the mean quality which is represented by PSNR (dB) and the horizontal axis is the number of frames. Figure 5a-d show the mean quality of three algorithms for Coastguard sequence in all cases, where nonscalable is nonscalable coding algorithm, Simplex is a simplex method and BitAlloc is the greedy algorithm. As shown in Fig. 6a-d, the video quality of nonscalabe is the worst and the video quality of Simlex and Bit-Alloc is very similar. Compared to Fig. 5 and 6 shows the corresponding quality improvement. The least quality improvement between Simplex, BitAlloc and Nonscalabe isnt less than1dB and the most one is more than 7 dB.
Table 1: | Parameters of the four experiment cases |
Fig. 5: | The mean quality of three algorithms for (a) Case 1, (b) Case 2, (c) Case 3 and (d) Case 4 of coastguard sequence |
Fig. 6: | The Stat of quality improvement of the coastguard sequence; (a) Case 1, (b) Case 2, (c) Case 3 and (d) Case 4 of costguard sequence |
Table 2: | The stat of mean quality improvement between BitAlloc and Nonscalable (unit:dB) |
Table 3: | The mean run time in all cases (unit:ms) |
Table 2 shows the more comprehensive mean quality comparison. The similar results are gotten and in all cases, the least quality improvement between BitAlloc and the Nonscalable isnt less than 1.2 dB and the most one is more than 5.2 dB. Table 3 shows the comparison result in run time between Simplex and BitAlloc and as shown in Table 3, BitAlloc is efficient and the run time is 1/3000 times less than that of Simplex.
According to the architecture of streaming media system, a serial scheduling and a parallel scheduling algorithm are proposed for multi-video-sources. In serial scheduling algorithm, only a service peer transmits the streaming data in the same moment and the multiple video sources work in turn. The theory of serial scheduling algorithm is relatively simple and is easy to understand without the experiment results. The scheduling problem of multiple video sources is relatively complex. It is modeled as a NLP and is converted to a GLP. In the implementation, the greedy strategy is introduced. The experiment results show the video quality of the parallel scheduling called BitAlloc and Simplex is similar and is much better than that of NonScalable. The reason is the bandwidth of receiving peer is made full use in BitAlloc and Simplex. However, the BitAlloc is much shorter than the Simplex in run time because the greedy strategy is introduced in the implementation of BitAlloc. The algorithms are very suited to the mobile P2P video streaming system.
This study is supported in part by National Natural Science Foundation of China under Grant No.60673179 and Natural Science Foundation of Zhejiang Province under Grant No. Z106727.