Guangsheng Feng
email: fengguangsheng@hrbeu.edu.cn

Huiqiang Wang
email: wanghuiqiang@hrbeu.edu.cn

Qian Zhao
email: zhaoqian@hrbcu.edu.cn

Hongwu Lv
email: lvhongwu@hrbeu.edu.cn

An Adaptive Channel Sensing Approach Based on Sequential Order in Distributed Cognitive Radio Networks

We design an efficient sensing order selection strategy for distributed Cognitive Radio Networks (CRNs), where multiple CRs sense the channels sequentially for spectrum opportunities according to a channel Latin Square. We are particularly interested in the case that CRs' quantity is more than the available channels', where traditional approaches will have high probabilities of collision. We first introduce a system model and an adaptive sensing threshold for available channels which is estimated according to the sensing probability of the specific sequential order. Then, we propose a channel sensing and access strategy that can adjust its sensing and access probabilities based on the crowded degree of sequential order. Last, we conduct extensive simulations to compare the performance of our approach with other typical ones. Simulation results show that the proposed scheme achieves an outstanding performance on channel utilization in the case of heavy channel workload.

Introduction

The rapid growth of new wireless communication services is now facing the difficulty of no enough available spectrum resource due to the fact that the fixed spectrums have been granted to some licensed entities exclusively. According to tremendous statistics [START_REF] Khan | Autonomous sensing order selection strategies exploiting channel access information[END_REF][START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF][START_REF] Khozeimeh | Brain-inspired dynamic spectrum management for cognitive radio ad hoc networks[END_REF][START_REF] Salami | A comparison between the centralized and distributed approaches for spectrum management[END_REF], a great deal of allocated spectrums are severely underutilized. According to this fact, a new technology, namely Cognitive Radio (CR), is contrived, which enable wireless services to operate over those licensed but temporally or geographically unused spectrums through secondary opportunistic access. Cognitive Radio Networks, abbreviated as CRNs, are built on the platform of Cognitive Radio, where primary users (PUs), i.e., the licensed users, have arbitrary rights to transmit over those licensed channels whenever necessary. However, the secondary users (SUs) or CR nodes must perform spectrum sensing to attain transmission opportunities under the premise of protecting PUs' communications. Due to the hardware advancement, most of the wireless terminals are able to sense more than one channel within a same transmission slot, which is also our concern in this paper.

For the arbitrary PUs' rights to use licensed channels, a proper sensing mechanism should be designed to ensure a lower rate of transmission collisions among CRs. This mechanism can also evacuate the occupied channels immediately once some PU reclaims them, even if there are some SUs' communications over them. Provided a centralized coordinator and a common control channel (CCC), every CR may achieve a high efficiency of channel sensing and allocation. Otherwise, each of them has to sense the spectrum opportunity independently and then accesses an idle channel depending on the sensed results. In this case, each CR hunts for the opportunities of access channel by periodic or sequential channel sensing. In the first approach, each CR senses a specific channel first and then transmits over it if available. Otherwise, the CR has to wait until the next transmission slot and repeat this process periodically. In the second one, in order to find some available channels, each CR has to sense the channels sequentially according to an elaborated order designed in advance. After spectrum sensing, each CR makes its own decision on whether to sense the next channel continually or to start transmission based on the sensed results. Contrast to the periodically sensing strategies, the sequential approach allows a CR to identify an idle channel quickly by sensing more than one channel successively. If the sensed channel is occupied by other entities currently, there is little time delay before sensing the successive channels. Due to the above justifications, sequential channel sensing is of our concern in this paper.

Traditional researches have mainly focused on improving the throughput of CRNs. However the majority of them have a common assumption or implied assumption that the temporal idle channels could accommodate the majority of CRs, and only in this case some scheduling approaches could achieve a better performance. For example, Khan's work [START_REF] Khan | Autonomous sensing order selection strategies exploiting channel access information[END_REF] has an excellent performance under the condition that the channel's quantity is not less than the CRs', which has been demonstrated in our experiment in Section 5, but Khan's contribution inspires our work greatly. On the basis of Latin Square utilized in [START_REF] Khan | Autonomous sensing order selection strategies exploiting channel access information[END_REF], we are interested in the sequential channel sensing strategy without a centralized coordinator under the case of heavy channel workload, i.e., more CRs but fewer available channels.

In this paper, we propose a distributed and sequential sensing approach in a decentralized CRN on the basis of Khan's approach and random access. The contributions of our work are summarized as follows. First, a dynamic sensing threshold for available channels is proposed, which can reflect the crowded degree of a specific sequential channel order. In consideration of the CRs' computation capabilities, the threshold adjustment should be simple, dynamic and low complicated. Once the quantity of sensed available channels reaches the threshold, the related CR will randomly make a decision on whether to choose one channel or to observer continuously. If lots of CRs are crowded on a common sequential order, our approach prefers observation to transmission. Otherwise, there will be a mass of collisions among those CRs, resulted in all the frames invalid as well as a whole transmission slot wasted. Furthermore, if a CR gets a spectrum opportunity and transmits successfully, its access probability to the sequential channel order will be increased; otherwise it will be decreased correspondingly at the next transmission slot. Meanwhile, the sensing threshold of available channel is updated based on the transmission result, i.e., success or failure on this sequential channel order.

The remainder of the paper is organized as follows. In Section 2, we introduce the related work of interest. In Section 3, we design a distributed system model, including the system process mechanism, the stop condition of sensing, the threshold of available channels required to sense, and the collision avoidance approach. In Section 4, we evaluate our proposed design at different channel workload through numerical experimental results. Finally, Section 5 concludes the paper.

Related Work

To solve the open problem of spectrum sensing and channel access in distributed CRNs, lots of researches have been conducted and some typical frameworks have been proposed, such as the work in [START_REF] Akyildiz | A survey on spectrum management in cognitive radio networks[END_REF][START_REF] Khozeimeh | Brain-inspired dynamic spectrum management for cognitive radio ad hoc networks[END_REF][START_REF] Salami | A comparison between the centralized and distributed approaches for spectrum management[END_REF], where the issue of Opportunistic Spectrum Access, abbreviated as OSA, is still a hot issue.

In order to attain more spectrum opportunities, each CR has to perform periodic sensing or sequential sensing under the premise of protecting PUs' transmission. Centralized and decentralized approaches are two typical branches in dealing with such problems. In centralized ones, a coordinator is required to schedule all CRs' sensing and transmission activities, such as in [START_REF] Fan | Channel sensing-order setting in cognitive radio networks: A two-user case[END_REF][START_REF] Liu | Traffic-aware channel sensing order in dynamic spectrum access networks[END_REF]. The work in [START_REF] Fan | Channel sensing-order setting in cognitive radio networks: A two-user case[END_REF] takes the statistical features of channel availabilities into consideration, and attains an optimal sensing sequential order with the assistance of coordinator, but this scheme is only suitable for two CRs existed. If lots of CRs are desired to communicate simultaneously, a heavy workload on channels will definitely deteriorate the network performance due to massive collisions. The work in [START_REF] Liu | Traffic-aware channel sensing order in dynamic spectrum access networks[END_REF] is established on an assumption that CRs and PUs cooperate with each other, where each CR reports its channel sensing result to a centralized Dynamic Spectrum Access (DSA) base station. Therefore, the overall throughput will be maximized through scheduling each CR's transmission opportunity by the DSA. In consideration of DSA unknowing all the operation parameters of PUs, this work proposed a sequential channel sensing order based on estimated traffic. However, all CR devices may not be managed by the same service provider in actual scenarios, and hence it is impossible to attain an optimal scheduling strategy with several different coordinators.

Sensing channel in CRNs with a distributed manner is another branch. Traditional researches are mainly focused on studying periodical sensing strategies, which are easy to implement especially only one authorized channel existed [START_REF] Liang | Sensing-throughput tradeoff for cognitive radio networks[END_REF]. Moreover, these approaches are easily extended to multi-channel scenarios. In other words, in a given slot, a CR selects a channel to sense in a random way or according to its prior knowledge, and then it accesses this channel to transmit if available. Otherwise, this CR should stay quiet in the whole transmission slot. In this point, a distributed learning and allocation approach is investigated in the work [START_REF] Anandkumar | Opportunistic spectrum access with multiple users: learning under competition[END_REF][START_REF] Anandkumar | Distributed algorithms for learning and cognitive medium access with logarithmic regret[END_REF], where an adaptive random selection strategy on orthogonal channels is employed. The implementation of this approach is simple but high collision probability.

Using sequential channel order to sense spectrum opportunity has become a hot issue [START_REF] Theis | Rendezvous for cognitive radios[END_REF], in which a CR probes multiple channels one by one with an elaborated order in a given time slot. Generally, high throughput and low collision are two main objectives of system optimization [START_REF] Jiang | Optimal selection of channel sensing order in cognitive radio[END_REF][START_REF] Chang | Competitive analysis of opportunistic spectrum access strategies[END_REF][START_REF] Cheng | Simple channel sensing order in cognitive radio networks[END_REF][START_REF] Huang | Optimal channel sensing order for various applications in cognitive radio networks[END_REF][START_REF] Pei | Energy-efficient design of sequential channel sensing in cognitive radio networks: optimal sensing strategy, power allocation, and sensing order[END_REF][START_REF] Li | Almost optimal dynamicallyordered channel sensing and accessing for cognitive networks[END_REF][START_REF] Lai | Opportunistic Spectrum Access with Two Channel Sensing in Cognitive Radio Networks[END_REF]. In the work [START_REF] Jiang | Optimal selection of channel sensing order in cognitive radio[END_REF][START_REF] Chang | Competitive analysis of opportunistic spectrum access strategies[END_REF], a low-load approach jointing transmission optimization is proposed to sense channels sequentially. The priori knowledge of authorized channels is not necessary in this approach but requires perfect bandwidth and data rate. The work [START_REF] Cheng | Simple channel sensing order in cognitive radio networks[END_REF] proposes a simple channel sensing order in multi-channel CRNs without the prior knowledge of PUs' activities, where all CRs sense the channels according to the descending order of their achievable rates. However, this approach is only suitable for OFDM surroundings, and also requires all channel gains in advance.

In the work [START_REF] Huang | Optimal channel sensing order for various applications in cognitive radio networks[END_REF], the statistics characteristics of Signal-to-Noise Ratio for each channel are explored using pilot signals and PU's activities. Based on the fluctuating nature of heterogeneous channels as well as the QoS requirements of various applications, two approaches for channel sensing order are proposed, which are suitable for real-time and best-effort applications respectively. Nevertheless, a Cognitive Pilot Channel, abbreviated as CPC, is required to exchange control information between CRs and the base station. The work [START_REF] Pei | Energy-efficient design of sequential channel sensing in cognitive radio networks: optimal sensing strategy, power allocation, and sensing order[END_REF] is focused on identifying the sensing order and sensing-access strategy such that it can achieve the maximum of energy efficiency. This problem is formulated as a stochastic sequential decisionmaking process and solved by means of dynamic programming. In addition, the longterm statistical features and short-term diversity features [START_REF] Li | Almost optimal dynamicallyordered channel sensing and accessing for cognitive networks[END_REF], as well as the fast channel sharing [START_REF] Lai | Opportunistic Spectrum Access with Two Channel Sensing in Cognitive Radio Networks[END_REF] are taken into account.

Recently, an efficient strategy for sensing order selection in distributed CRNs surroundings is proposed in Khan's work [START_REF] Khan | Autonomous sensing order selection strategies exploiting channel access information[END_REF], where two or more autonomous CRs sense the channels sequentially (in some sensing order) for spectrum opportunities.

The key contribution of this work is the adaptive persistent sensing order selection strategy in the case that CRs with false alarms autonomously select the sensing orders. This approach may achieve a better performance only when the quantity of CRs is not more than the quantity of available channels.

Different with existing work, we propose a novel sequential order strategy for sensing multiple channels in distributed CRNs jointing Khan's work and random access, but the two works have essential differences. Given that the sensing duration for a single channel is much shorter than the transmission duration, it is worth to attain a much lower collision probability at the cost of part transmission time, which is the foundation of this work.

3

An Adaptive Model for Multiple Channels Sensing

System Model

In a distributed CRN, M CRs and N authorized channels are coexisted, which are denoted as

12 { , , , } M CR CR CR  CR and 12 { , , , } N C C C  C
respectively. If some channels are idle and sensed simultaneously by some CRs, they could transmit over those channels. In this case, if a PU reclaims one of the channels occupied by some CR, it will be evacuated by the related CR at once, which is consistent with the basic principle of Cognitive Radio. Given that all PUs and CRs employ the same time slot system as figure 1 shown, a CR maybe have experienced i sensing sub-slots when k idle channels are found, where k is the sensing threshold of available channels, i.e., a CR is required to find k idle channels and then makes a decision on whether to transmit or sense continually. The maximum of sensing duration is an allowable sensing interval, and the sensing process will be stopped and stay quiet if there is no any idle channel found until this upper bound. A PU's communication activity starts only in the beginning of a time slot and last to its end.

Fig. 1. Multiple channels access with the same time slot system

Similar to Khan's approach, all channels are organized as a form of Latin Square such as in(1):

1 2 3 1 2 3 4 1 3 4 5 1 2 1 2 2 1
, , ,

N N N C C C C C C C C C C C C C C C C C C C C            CS , , , , , , , , , , , , , , , , , NN N
where there are N*N elements and each row CS i (i=1,2,…,N) stands for a sequential channel order whose elements are consisted of CS ij (j=1,2,…,N). Every CR maintains a sensing probability for each CS i , i.e., ( )

( ) { , 1, 2,..., } CS CS i P p i N 
, which the CR senses sequential channel order CS i according to. At the beginning, each CR will select some CS i according to the probability () 11

CS i CS p N N 
. With the process going, the () CS i p will be updated according to its transmission and collision states, the objective of which is lowering the sensing probability to crowded channel orders. Note that the specific adaptive updating approach for () CS i p will be elaborated in next section. Due to the limitation of hardware devices, sensing and transmission could not be conducted simultaneously.

This model is established on the analysis of contending spectrum resource and one CR will make a decision on communicating over an idle channel only when k available channels are found. If two or more CRs are crowded at the same sequential channel order, it is required to sensing more available channels before making a transmission decision. Otherwise, a smaller number of available channels can help make a transmission decision. As shown in figure 2, C 1 ,C 2 ,C 3 and C 4 four channels are existed in a CRN, whose front part is a Latin Square based on channels, and its columns stand for sensing sub-slots, such as Sense 1 to Sense 4. In a transmission slot, a CR should find some idle channels first and then transmit in the remaining time of this slot. Suppose that CR 1 and CR 2 are crowded at the same CS 1 to perform sequential channel sensing simultaneously. In this case, if both CRs transmit immediately once they find one idle channel, a collision event between them is destined to occur. On the contrary, if they start their transmission when more than one idle channel is found, such as C 1 and C 2 available, they maybe avoid this collision event for CR 1 choosing one idle channel but CR 2 choosing the another idle one. Instinctively, the collision probability at the same sequential channel order is decreased.

Fig. 2. Schematic diagram of channel sensing

Stop Condition and Sensing Threshold for Available Channels

In this paper, we mainly concern the distributed approach for sequential channel sensing and there is no possibility of cooperative communications among CRs as well as PUs. Given that the sensing threshold for available channel is k, each CR will sense the sequential channel order CS i successively, i.e., {CS i1 , CS i2 ,…,CS im }, based on its sensing probability () CS i p until k available channels are found. Afterwards, the CR makes a decision on whether to transmit or to sense continuously. In contrast to existing work, we do not consider the traditional stop condition that once an idle channel is found, the process will be transferred to transmission from channel sensing. In the case of heavy channel load, i.e., more CRs but fewer available channels, two or more CRs are crowded at the same sequential channel order which leads to a high rate of collision correspondingly. If we continue to sense until k available channels (at least one) found, each CR on this channel order will have an opportunity to choose a different channel C j to transmit according to its access probability ( , )

CH i j p CS C .
Therefore, the value of k is sensitive to the collision probability. If it is too small, more collision will be caused, but on the contrary, the overall sensing time will be increased and the transmission time is shortened correspondingly.

As discussed above, () CS i p is the foregoing sensing probability that a CR attends at sequential channel order CS i , which is estimated according to its transmission success or not on CS i . A smaller of () CS i p stands for a higher collision probability on CS i . On this basis, the threshold k of available channels could be estimated as (2):

k= () min{ 1/ , } CS ia pC   (2)
where C a is the total quantity of available channels. Therefore, k's value stands for the crowded degree of the current channel order. If k equals to 1, our approach is simplified to Khan's. In conclusion, the stop condition of sensing channel is that k available channels have been found by the current CR.

Mechanism of Collision Avoidance

In a distributed CRN, collision events will occur frequently due to different CRs contending spectrum opportunities as well as lacking coordinated mechanism among CRs. If two or more CRs are crowded at the same sequential channel order, each CR may attain a similar sensing result and they surely collide with each other even the idle channels being found. In this case, all the transmission frames will be corrupted.

To solve those problems, we propose a dynamic collision avoidance mechanism in this paper. Suppose that a CR senses on sequential channel order CS i , and do not take transmission activity until k available channels are found, where k is estimated according to section 3.2. If the specific quantity channels are found, the CR will randomly make a choice to transmit or to sense continuously. If continuous sensing is selected, the similar decision will be made in next sensing round. In other words, once k available channels are found, the CR faces two choices:  Select channel C j to transmit based on ( , )

CH i j
p CS C that denotes the probability of selecting channel C j :

2 ( , ) (1 )
j CH i j r p CS C kk    ( 3
)
where k is the sensing threshold of available channels and r j is the index number of channel C j in current available channel set. As shown in(3), the last available channel in sensing result set has the highest access probability. Let r (r=1,2,…,k) denotes the index number in available set, and I r is the subscript of some channel, i.e., Ir C C . Therefore, Ik C is the last element and ( , )

CH i Ik p CS C is 2 2 ( , ) (1 )
(1 )

CH i Ik k p CS C k k k      (4)
To sum up, the access probability of each element in the available set is sensitive to its index number in this set as well as the total quantity k.  Continue to sense at the current sequential channel order CS i .

If the first choice is selected, i.e., transmit over channel C j , the following two cases maybe happen.

Case 1:If there is no collision over channel C j during the transmission interval, this time of transmission is successful, which can be inferred from whether the related ACK is correctly received or not. In this case, the sensing probability CS j , whose first item is C j , is increased correspondingly:

( ) ( ) () () ( ) ( ) () ' 1 , if ' 1 ' CS CS j j j CS CS j CS CS jj k j k j CS qj qj pp p p pp p                  (5)
where () '

CS j p
is the sensing probability of CS j at the last transmission slot and 0 j   denotes the augmentation of sensing probability to CS j at this transmission slot. The value of j  should meet the requirement

() 1/ 1/ ' j CS jj p p K          ,
which means that the sensing threshold of available channels should be increased by

() j CS K
such that the hit rate of channel C j will be increased correspondingly. In this updating process, if () '1

CS jj p   holds true, the sensing probability to CS j will be set to 1 and other one be set to 0, i.e., () CS kj p  =0. Case 2:If the ACK is not received correctly, it is deemed that a collision occurs on channel C j . In this case, the sensing probability to sequential channel order CS j will be decreased, but others will be increased as shown in(6):

( ) ( ) () () ( ) ( ) () ' 1
, s.t., ' 0 '

CS CS j j j CS CS j CS CS jj k j k j CS qj qj pp p p pp p                  (6)
Similarly, the value of 0 j   should meet the requirement

() 1/ ' 1/ j CS jj p p K         
such that the hit rate of CS j and C j will be decreased. If there is a contradictory between the two inequalities

() '0 CS jj p   and
() 1/ ' 1/ j CS jj p p K         
, the former one should be assured first.

In case 1, it is possible that a CR continues to sense at the current sequential channel order CS i . In this case, this CR starts to sense from the first element in CS i in next sensing round, but those channels that have been found busy in the first sensing round will be omitted. Similarly, the process will transfer to transmission or selection decision when k available channels are found. When the whole time of sensing rounds reaches to the upper bound, i.e., the maximum of sensing duration, the sensing process will be stopped at once. As an example shown in figure 3, in the first sensing round (Round 1), CR 1 , CR 2 , CR 3 and CR 4 employ the same order CS 1 <C 1 , C 2 , C 3 , C 4 , C 5 > to sense k (k=3) available channels. As a result, C 2 is busy and C 1 、C 3 and C 4 are idle. In this case, if CR 1 selects channel C 1 to transmit but others decide to sense continuously, C 3 , C 4 and C 5 are found available and C 1 is observed in this round. In this case, if CR 2 and CR 3 make a decision on transmission over C 3 , a collision happens. Therefore, in the next transmission slot, CR 2 and CR 3 will decrease the sensing probabilities to CS 3 < C 3 ,C 4 ,C 5 ,C 1 ,C 2 ,>, and meanwhile increase the others.

Instinctively, what we do can lower the collision probability in contrast to immediately transmission while one available channel is found.

Fig. 3. Illustration of sense, collision and transmission in a transmission slot

Our proposed adaptive multiple channels sensing strategy can be summarized as the following pseudo-code algorithm CRN_MCST, which is executed in each CR independently and there is no any information exchanging among them.

Each CR will execute algorithm CRN_MCST one time in every single transmission slot. In initialization stage, the sensing probabilities to all sequential channel order are identical. With the iterating of transmission, each CR independently make a judgment on whether the current sequential channel order is crowded or not, and then adjust its sensing probability accordingly. In line 2-3, the threshold k of available channels sensing is calculated based on the sensing probability, and meanwhile a sequential channel order is selected from the channel Latin Square, i.e., CS i . In line 4-8, the CR senses the sequential channel order successively, in which all the available channels are stored into the pre-allocated buffer. This process will be executed repeatedly until k available channels found or all the items in CS i have been checked. Thus, the complexity of line 4-8 is proportional to the total channel quantity, i.e., O(n). In the process of line 9-20, the CR makes a decision on which channel should be selected for transmission, and the sensing probability and access probability are also updated according to the transmission result. The time complexity is proportional to buffer size, thus it is O(k) and k<=n. In line 21-22, it is the case that no available channels are found and the CR will stay quietly in the whole transmission slot. To sum up, the time complexity in a transmission slot is O(n).

Algorithm: CRN_MCST Initialization: The sensing probability vector P (CS) , and each () Store the CS ij into the buffer_free; 8.

END WHILE

9.

WHILE sizeof(buffer_free)>0 10.

Make a decision on whether to transmit or continue to sense randomly; 11.

IF deciding transmission THEN 12.

Select C j from buffer_free to transmit based on E.q.(3) 13.

Set transmit_flag=true and Transmit at the remaining transmission slots 14.

IF transmission is successful at C j in CS i THEN 15.

Increase the probability CS j based on sensing probability E.q.(5) ; 16.

ELSE decrease the probability CS j based on sensing probability E.q.(6); 17.

Evacuate the buffer_free; // CR will transmit at the remaining period 18.

ELSE //continue to sense the free channel in buffer_free 19.

Goto step 2; 20.

END WHILE

Experiments and Analysis

In order to verify the performance and compare with other typical approaches, some numerical experiments has been conducted in this section, where the mainly parameters in our experiment are similar to Khan's approach. The channel busy probability Pu is set 0.0, 0.1, 0.3 and 0.5, such that we can check the performance of different approaches at different channel workloads. The total channel quantity is 10 and the quantity of CRs are various from 2 to 20. The performance of channel utilization can be inferred from the wasted ratio of transmission slot, including collision interval and idle interval. Moreover, we set 50 transmission slots in each time experiment and total 10 experiments are conducted. Thus, we have attained 100 times experimental data. Meanwhile, we set 11 sub-slots as a transmission slot, i.e., if a CR has sensed the last item in current sequential order, there is only one sub-slot for transmission. The experimental results are shown in figure 5 -figure 8.

Figure 5 and figure 6 are the comparisons between our approach and Khan's. Khan's approach has an excellent performance under the case that there is a light load with a fewer number of CRs on the channels, where the wasted ration of transmission is no more than 20%. While the CR quantity is more than 10, the wasted ratio is soaring. Even all the channel are not occupied by PUs, i.e., Pu=0.0, the wasted ratio reaches 60% with 20 CRs. But in the case of Pu=0.5, the wasted ratio is about 33% in Khan's approach. Figure 6 shows the experimental result of our approach. It is obvious that the proposed approach has a better overall performance compared with Khan's, and the wasted ratio is constrained about 10% at different probabilities of Pus. Only when the CR quantity is 2 or 3, the performance is not superior to Khan's. Fig. 6. The proposed method at different Pus with various CR quantities Figure 7 shows the comparison at the channel busy probability Pu=0.1. Only when the CR quantity is less than channel quantity, Khan's method has a better performance. After that point, this approach has an intolerable increasing on channel wasted ratio. On the contrary, our approach remains a comparative stable wasted ration about 10%, only when the CR quantity is 2 or 3, the performance is poor. In the case of heavy channel workload, our proposed approach will be a quite effective complement to Khan's approach. In those three approaches, the Random LS strategy [START_REF] Cheng | Simple channel sensing order in cognitive radio networks[END_REF] has the least performance and the channel wasted ratio is reached 70% when there are 20 CRs in the network.

Conclusion

In this paper, we have investigated the distributed channel sensing strategy in a CRN environment with heavy load channels and obtained some important observations. In the system model, a sensing threshold for available channels is estimated based on the crowded degree of the current sequential channel order. On this base, each CR can adjust its sensing probability to sequential order and access probability to a channel according to whether this transmission success or not. Moreover, we presented an algorithm with low computational complexity, in which the process of each CR sensing the sequential channel order and deciding channel to transmit is elaborated in detail. Simulation results demonstrate the effectiveness of our proposed approach.

Fig. 4 .

 4 Fig. 4. Algorithm CRN_MCST: multiple channel sense and transmission

Fig. 5 .

 5 Fig. 5. Khan's method at different busy probabilities of channels with various CR quantities

Fig. 7 .

 7 Fig. 7. The comparison between different approachesWhen there are 10 CRs, each CR could attain an almost equitable transmission chance about 10% in all those three approaches, and all of them have achieved a well fairness, as shown in Figure8.

Fig. 8 .

 8 Fig. 8. The comparison in transmission ratio of different CR nodes

  1/ , 1,2,...,

		i p	CS	n i 	n
		The channel matrix CS with Latin Square form;
		buffer_free is empty;// used for store the available channels sensed
		transmit_flag=false;
	1.	BEGIN
	2.	i CS i is selected from CS based on () CS p
	3.	Calculate k based on E.q.(2)
	4.	WHILE ! endof(CS i ) && sizeof(buffer_free)<k //k is the threshold of free channels
		sensed by the current CR
	5.	IF CS ij is busy THEN j++;
	6.	ELSE
	7.

Acknowledgments

. This work was supported in part by the Research Fund for the Doctoral Program of Higher Education of China under Grant 20122304130002, the Natural Science Foundation in China under Grant 61370212, the Natural Science Foundation of Heilongjiang Province under Grant ZD 201102 and F201037, the Fundamental Research Fund for the Central Universities under Grant HEUCFZ1213 and HEUCF100601, and Postdoctoral Science Foundation of Heilongjiang Province under Grant LBH-210204.


Changli Zhou
email: zhouchangli888@gmail.com

Chunguang Ma
email: machunguang@hrbeu.edu.cn

Songtao Yang

Peng Wu

Lin Lin Liu

A Location Privacy Preserving Method Based on Sensitive Diversity for LBS

A user's staying points in her trajectory have semantic association with privacy, such as she stays at a hospital. Staying at a sensitive place, a user may have privacy exposure risks when she gets location based service (LBS). Constructing cloaking regions and using fake locations are common methods. But if regions and fake positions are still in the sensitive area, it is vulnerable to lead location privacy exposure. We propose an anchor generating method based on sensitive places diversity. According to the visiting number and peak time of users, sensitive places are chosen to form a diversity zone, its centroid is taken as the anchor location which increases a user's location diversity. Based on the anchor, a query algorithm for places of interest (POIs) is proposed, and precise results can be deduced with the anchor instead of sending users' actual location to LBS server. The experiments show that our method achieves a tradeoff between QoS and privacy preserving, and it has a good working performance.

Introduction

Location Based Serv ice (LBS) brings convenience to people's lives , at the same t ime, it also poses a risk of location privacy leakage. Location based query is a widely used LBS, a user sends a query request with her current location to LBS provider (LSP) to get places of interest (POIs). Such as "find the K nearest neighbor restaurants around me" or "find a ll the restaurants in the range of R kilo meters", the former one is called KNN query and latter one is range query. Due to the spatial and temporal relevance, an exposure of location privacy may lead deeply privacy leakage, such as a user's home address, hobbies, health condition and so on. Location privacy is significantly important to us and should be protected carefully.

Places on a user's trajectory can be div ided into two kinds: passing -by places and staying-at places. A mobile user issues LBS query with her current location at any time in a trajectory. A passing-by place has no relationship with a user, it only means a user has passed by a location without any semantic association. But a staying-at place, especially a sensitive place, has semantic association with a user staying at it, such as a user is staying at an infectious hospital.

Location obfuscation is a general protecting method for location privacy preserving. Such as constructing cloaking region to achieve k-anonymity [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[C]//Proceedings of the 1st international conference on M obile systems, applications and services[END_REF][START_REF] Gedik | Location privacy in mobile systems: A personalized anonymization model[END_REF][START_REF] Chow | Trajectory privacy in location-based services and data publication[END_REF], as shown in Fig 1, user C sends her actual location to an anonymous server (AS), then AS expands her actual location to a rectangle R 2 including 2 other users, and R 2 will be sent to LSP for POIs instead of her actual location. But there is a problem, if the cloaking region is in a sensitive area, such as dash line rectangle in Fig. 2. A query is sent with R 2 means the user is in a hospital. And when a user stays or moves a short distance in a sensitive area, all her cloaking reg ions may be included in it. Location diversity is a solution that requires users in a cloaking reg ion to appear in diverse places, but that may lead a large cloaking reg ion, such as R 3 . Another protecting method is using fake locations [START_REF] Kido | An anonymous communication technique using dummies for location-based services[C]//Pervasive Services[END_REF][START_REF] Lu | Pad: Privacy -area aware, dummy-based location privacy in mobile services[END_REF], that is sending an actual location accompanied with some fake locations, and all the locations will be used in query operations, that brings too much burden to LSP. Then query methods with significant object [START_REF] Hong | An architecture for privacy -sensitive ubiquitous computing[END_REF] or anchor [START_REF] Yiu | Spacetwist: M anaging the trade-offs among location privacy, query performance, and query accuracy in mobile services[C]//Data Engineering[END_REF] are proposed, they have more improve ments and more precise query results. Especially, SpaceTwist [START_REF] Yiu | Spacetwist: M anaging the trade-offs among location privacy, query performance, and query accuracy in mobile services[C]//Data Engineering[END_REF] is an effective method to get KNN POIs without providing a user's actual location to LSP. But these methods have the same drawback, wh ich is if the fake locations or anchors are still p icked in a sensitive area, location privacy of a user will be leaked anyway.

Staying at a sensitive place causes a semantic association with a user, continuous sensitive places lead to deep-going leakages [START_REF] Pellegrini | You'll never walk alone: M odeling social behavior for multi-target tracking[C]//Computer Vision[END_REF][START_REF] Huo | You can walk alone: trajectory privacy -preserving through significant stays protection[C]//Database Systems for Advanced Applications[END_REF]. We focus on the privacy preserving when a user is staying at or moving short distance around a sensitive place. The contents and contributions of this paper are as follows:

1).We propose a location privacy preserving method based on sensitive places diversity when a user is staying at a sensitive place. A center server (CS) generates a diversity anchor for a user. The diversity anchor is used to replace a user's actual location. CS sends a query with the anchor. The diversity anchor is in the overlap area of several sensitive places, which increases uncertainty of a user's actual location.

2).We propose a query algorithm with the diversity anchor. In a query request, a diversity anchor is sent to LSP instead of a user's actual location. LSP takes the anchor as a centroid and returns a candidate POIs set to CS, and CS can deduce precise result of K NN POIs for a user. Without providing any user's actual location, our algorith m achieves location privacy preserving and gets precise KNN POIs for a user.

Related works

In order to achieve location privacy preserving, a user obscures her actual location before getting LBS. Gruteser et al [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[C]//Proceedings of the 1st international conference on M obile systems, applications and services[END_REF] brought in k-anonymous idea from database for LBS privacy preserving. Mokbel et al [START_REF]Towards privacy -aware location-based database servers[C]//Data Engineering Workshops[END_REF] proposed an architecture with center server(CS), CS is between users and LSP, most of the CSs are credib le. CS cloaks a user's actual location and returns refined results. Chow and Mokbel [START_REF] Chow | A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C][END_REF][START_REF] Chow | Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[END_REF] proposed a P2P architecture without CS, it removes bottleneck when CS faces lots of users.

Anonymity is achieved by these methods, but if users crowd t ogether in a place, cloaking regions may still in a s mall area, in extreme case they are at the same spot. To solve this problem, Bamba et al [START_REF] Bamba | Supporting anony mous location queries in mobile environments with privacygrid[END_REF] introduced l-diversity idea from data publication into location anonymity, they proposed a cloaking method whic h satisfies location diversity. Xue et al [START_REF] Xue | Location diversity: Enhanced privacy protection in location based services[M ]//Location and Context Awareness[END_REF] proposed a location diversity method to ensure each query can be associated with at least l different semantic places. Xu et al [START_REF] Xu | Location privacy protection through anonymous cells in road network[END_REF] proposed an anonymous cell with diversity roads. Yang et al [1 8] proposed cloaking cycle and forest which include diversity roads to ensure that a user locates at diversity roads equally in a cloaking cycle. Meng et al [START_REF] Huo | You can walk alone: trajectory privacy -preserving through significant stays protection[C]//Database Systems for Advanced Applications[END_REF] p roposed sensitive trajectory location protection method in data publication. Liu [START_REF] Liu | Query l-diversity in location-based services[C]//M obile Data M anagement: Systems, Services and M iddleware[END_REF] gives query l-diversity in location privacy preserving for the first time.

Using fake locations is another way to achieve protection. A general method is sending several fake locations in order to obscure a user's actual location [START_REF] Kido | An anonymous communication technique using dummies for location-based services[C]//Pervasive Services[END_REF][START_REF] Lu | Pad: Privacy -area aware, dummy-based location privacy in mobile services[END_REF][START_REF] Hong | An architecture for privacy -sensitive ubiquitous computing[END_REF][START_REF] Yiu | Spacetwist: M anaging the trade-offs among location privacy, query performance, and query accuracy in mobile services[C]//Data Engineering[END_REF]. A user sends a fake location in SpaceTwist [START_REF] Yiu | Spacetwist: M anaging the trade-offs among location privacy, query performance, and query accuracy in mobile services[C]//Data Engineering[END_REF], which is called "anchor", to LSP and the user deduces POIs result according to the returned candidate set. The main procedure is as follows:

As shown in Fig. 2, a solid "•" denotes a user's actual location, "×" denotes an anchor. A user sends a query with the anchor to LSP, LSP performs INN (incremental nearest neighbor) query to get POIs candidate set and then sends it to the user gradually. Firstly, LSP takes the anchor as the centriod of supply space to search POIs. When a POI is found in Fig. 2(b), the supply space expends and the demand space centred with user's location shrinks. As POIs are found gradually, SpaceTwist terminates when the supply space covers the demand space. Meng [START_REF] Huang | Coprivacy: A collaborative location privacy -preserving method without cloaking region[END_REF] and Gong [START_REF] Gong | Protecting privacy in location-based services using k-anonymity without cloaked region//M obile Data M anagement (M DM)[END_REF] have proposed improvement to make SpaceTwist achieve k-anonymity respectively. Both cloaking region and anchor will cause privacy leakage when they are still in a sensitive place. In this paper, we use an anchor referring to SpaceTwist, and ensure a user at sensitive place to p ick the anchor with location diversity. Based on the anchor, we propose a query algorithm to get precise KNN POIs result for a user.

We pick the arch itecture with a CS, CS is between users and LSP, as shown in Fig. 3. A user with a GPS sensor of her intelligent terminal sends her location and query to CS. CS co mputes an anchor and sends anonymous query with the anchor to LSP. LSP performs INN search in its database according to the anchor location and returns POIs candidate set to CS. CS deduces precise results to the user. Definiti on 1: There are 3 entity sets U,CS,LSP  , U k u  represents an energy constrained mobile user. CS i CS  is a central server, deployed at crowded location, it has stronger abilities. LSP is an LBS provider, which is powerfu l in energy and processing, it stores all POIs in its database. CS is credib le, users and LSP may be not. Definiti on 2: A user's query , , , ,  is a POI or a sensitive place. POIs also have semantic association with users, so we usually consider some POIs as sensitive places.

k uk u loc l C R  , k u is her identity,

Location privacy preserving method

Our method includes two main phases: the CS generates a diverse anchor for the user who is at a sensitive place, and query for KNN POIs with the anchor. The first phase contains sensitive location definition method based on users visiting frequency characteristics, and the anchor generating method is based on sensitive locaiton diversity. The second phase presents the query algorith m with a d iversity anchor.

Di versity anchor generating phase

We assign different sensitive weights based on users visiting number and visit ing time period firstly. The sensitive weights are used to generate a diversity anchor then.

Sensitive l ocation definition

Visit ing number and peak visit ing time period of a place re flect a sociality of a kind of people. When the users are staying at the place, the semantic associations will lead a privacy leakage of these users. For examp le, the visit ing users to a place becomes more in every weekday morning, it may be a company rath er than a bar, a user stays at this place may expose her working place. A p lace is often visited at n ight, it may be a bar rather than a hospital. Nearly all sensitive places have bigger visiting numbers and regular peak v isiting time. These may lead a correlation with a category of places, so we take visiting nu mber and peak v isiting time as main factors.

1 v 2 v 3 v 4 v i v k v i 

Fig.4. Road networks with POIs

As the sensitive places are distributed in road networks, a user always finds a path to reach a sensitive place. So when we discuss users visiting number, we consider sensitive places (or POIs) are on the edge of the road graph. We define a directed graph of road networks as ()

G = V,E , V is a set of vertexes, each i v  V has a visiting weight () ii v    . E is a set of edges,
jj i i i ki i ki v k i v k i ve               VV  (1)
i out i k out k v v v v     (2) Suppose a place i  on k i
vv has n users passed by in a certain time period of a day and the probability of staying-at users is p, so the users staying at a place i  on k i vv follows Po isson process with an arrival rate i np   . The probability of staying-at number X of users when X is greater than a threshold T X is:

T X TT T ( X ) 1 ( X ) 1 ... 0! 1! X ! e e e P X P X                 (3)
So each place can be assigned with the weight as:

()

T P X X     (4)
We choose typical time periods of a day, such as rush hour, leisure time and so on, to get a sensitive weights sequence of a place ()

i 1 2 3 n ( , , ,..., )       ,
n ii i n       (5)
If a place satisfies ()

i T R 



, we call it a sensitive place, T R is a sensitive threshold. The sensitive weights are used to generate diversity anchor in next section.

Anchor generating based on sensitive locati on di versity

In this section, we pick a user's neighbor sensitive places to form a diversity zone, the anchor is generated at the centroid of the zone, a user querying with the anchor improves the probability of staying at different sensitive places.

When CS chooses neighbor sensitive places for a user, we d ivide neighbor sensitive places into 3 categories:

A. Disparate places, this kind of places have disparate peak visiting time period, a user choose this place may lead severely uneven distributing probability of each sensitive places for a user, such as a hospital and a bar, so CS excludes these places.

B. High correlation p laces, this kind of p laces do not only have similar peak visiting time period but also shows a linear correlation with the sensitive place which the user is staying at. These places may be the same kind neighbor places, such as two neighbor bars. For achieving diversity, CS excludes these places.

C. Similar p laces, this kind of p laces have similar peak visiting time period but they are not the same places, choosing this kind of p laces ensures sensitive diversity.

There are other measures to pick diversity places, we focus on user visiting number and its variation tendency according to the sensitive weight sequence of a place ()

i 1 2 3 n
( , , ,..., )

      , wh ich we have discussed below Formu la (4).

CS has the sensitive weight sequences of all the POIs in its coverage area, one of the sequences of a place i  is denoted as ()

i i i i i 1 2 3 n ( , , ,..., )       , each () i 1i     at different
                    (6)
Formula ( 6) only filters the disparate places. If two sequences of i  and k 

show similar tendency, such as 2 simple examp les (2000, 400, 100) and (1000, 200, 50), they have similar variation tendency, and shows linear similarity, these may belong to category B. We exclude these places to guarantee sensitive diversity. We use Pearson correlation coefficient to achieve this goal, which represents the linearly dependent of two data sequences.

1 1 ( , ) 1 i k ik n j i j k ik j r n s s                    (7)
As shown in Formu la [START_REF] Lu | Pad: Privacy -area aware, dummy-based location privacy in mobile services[END_REF], i  和 i S are mean value and standard deviation respectively. The more || r approaches 1, the higher linearly dependent is . We exclude places of category B with high || r . There is no negative correlat ion (r<0) after the filter of Formula (6).

( , ) ( )

n ik i k j j j Dist        (8)
CS filters disparate places and high correlation places by Formula ( 6) and ( 7), the remain ing places satisfy sensitive diversity and refrains fro m inferring attack according to peak visiting time period difference. We rank the remain ing candidate places according to similar degree, as defined in Formu la [START_REF] Hong | An architecture for privacy -sensitive ubiquitous computing[END_REF], CS chooses better places to form a d iversity zone according to diversity degree. We use Euclidean distance to estimate the similar degree in the candidate set. The greater Euclidean distance is, the higher diversity degree of a neighbor sensitive place is. u loc l C R  , it picks a neighbor grid randomly, as shown in Fig. 5 (a), and clockwise get all the sensitive places in its neighbor grids, all the grids are in an angle range of 180  from the first grid, there is an angle limit because if the other sensitive places surround i  , i  will be the sensitive where the user is staying at. CS co mpares each sensitive place with i  using Formula ( 6) and [START_REF] Lu | Pad: Privacy -area aware, dummy-based location privacy in mobile services[END_REF], filters disparate places and high correlation places, and ranks the remaining places according to Formu la [START_REF] Hong | An architecture for privacy -sensitive ubiquitous computing[END_REF]. Finally, CS chooses l sensitive places to form a diversity zone and takes its centroid as the anchor location, l is sensitive diversity degree defined by the user in query request. The Algorithm is as follows: clockwise get all neighbor grids 6.

S  all the sensitive places in these grids In this section, we propose the picking method of sensitive diversity places according to user visiting number and its variat ion tendency. Then we use diversity places to form a d iversity zone, the anchor is the centroid of the zone. CS use s this anchor to replace the user's actual location and issues us ers' query with the anchor. We can find that the anchor can be reused by other users in the sensitive places which form a diversity zone, the reuse decreases the overhead of CS.

Query phase

In this phase, CS sends user's query request , , ,

i anchor CS loc C 
 with a diversity anchor. When LSP receives a query request, it takes the anchor as a dimcenter and executes INN search. LSP returns the POIs candidate set gradually to CS. CS performs Algorithm 2 to deduce precise KNN PoIs for a user. As show in Fig. 6(a), a user locates at q and q' is the diversity anchor, when the first POI is found, supply space (the dark grey cycle) expands and space (light grey cycle) shrinks. As POIs are found gradually, supply space covers demand space for the first time in Fig. 6(b), K POIs are found around the anchor. Then demand space updates, containing K POIs in its cycle and keeps its radius unchanged after the expand, as shown in Fig. 6(c) K=3. In Fig. 6(d-e), query procedure continues until supply space covers demand space for the second time, K POIs are found around user. The algorith m running at CS end and referring to SpaceTwist is as follo ws: Algorithm 2. CS performs the algorithm for KNN PoIs around a user at q 1. Procedure:K is defined by k u , uk q loc  , '

q' q' q (a)the first POI (b)first cover P1 q'   q P2 P4 P3 P1 q'   q P2 P4 P3 P1 q'   q P2 P4 P3 P5 P6 P5 P7 P8 P9 P10 P4 P1 P2 P3   q   (c)expand (
anchor q loc  ,  is the package capacity of PoIs returned from LSP 2. CS generates a max heap K W 3. insert K pairs of , NULL   into K W 4.   the top distance in K W // initialize demand space 5. 0  
// initialize supply space 6. send INN query to LSP with diversity anchor ' q 7. while ( , ') dist q q   do 8.

S  get next package of PoIs from LSP 9.

  get the maximum x ( ', ) dist q 
in S // update supply space 10.

for each w S   do

  then 12. K W  , ( , ) ww dist q   13. ( , ) w dist q    14.   get ( , ) K dist q  in K W 11. if ( , ) w dist q 
// update demand space 15. while ( , ') dist q q   do [START_REF] Gong | Protecting privacy in location-based services using k-anonymity without cloaked region//M obile Data M anagement (M DM)[END_REF].

S  get next package of PoIs from LSP 17.

  get the maximum ( ', ) u dist q  in S // expand supply space gradually [START_REF] Xue | A location privacy preserving approach on road network[J][END_REF]. if ( , )

u dist q    then 19. K W  , ( , ) hu dist q   20. terminate INN query 21. return bottom K PoIs in K W 22. End Procedure.
In our algorithm, demand space expands and covers at least K PoIs, which is the key point guarantees the user to get K PoIs around him nearly in 100% success rate. The query process will not terminate until supply space covers demand space again. As shown in Fig. 6(e), LSP returns 10 PoIs in total. Alogrithm 2 picks K=3 PoIs 2 5 7 { , , }    of them, the 3 POIs are around the user q, our algorith m is better than SpaceTwist. When we consider a user stay in a sensitive place, that means all the users are static or moves short distance, Algorithm 2 is snapshot query rather than continuous query, a user in a query procedure always uses one diversity anchor. As we known, a continuous query is composed of several snapshot queries, so Algorithm 2 is applicable for continuous query if continuous anch or sequence is generated. We will consider it in future work.

Performance anal ysis

In this section, we will discuss security in the procedure of diversity anchor generating and querying with the anchor, then we analysis the algorithm co mp lexity.

(1) analysis An anchor is chosen in the overlap region of several sensitive places, it increases the probability of a user appearing in different sensitive places, the user's location semantic privacy is preserved. The diversity sensitive places are filtered by Formula (6), the disparate places are d iscarded to ensure the user is staying at each places with equal opportunity. Formu la [START_REF] Lu | Pad: Privacy -area aware, dummy-based location privacy in mobile services[END_REF] filters the sensitive places which may be the same to the one a user is staying at, such as a user is staying at a hospital, CS choose neighbor other hospital for her, which reduces the diversity. At last, CS picks l sensitive places in the remaining places to form a d iversity zone, since the sensitive places is chosen fro m a randomly direction firstly and different users at the same sensitive place have different l-diversity degrees, so CS generates different anchors for users from the same place, that avoids inferring attacks which all the users us ing the same anchor are fro m the same sensitive place.

When CS generates an anchor according to l sensitive places around him, she is staying at each place with equal probability ( ) 1/ i p x l 

, so the information entropy of querying with this anchor one time is:

ll i i ii H q p x l l p x l      (9)
That is the ma ximu m informat ion entropy for a single t ime, an adversary is hard to correlate any anchor with a user at sensitive place.

(2) Co mplexity analysis of query algorith m Algorith m 2 is running at CS end, it compares the returned POIs fro m LSP, and decides when to terminate the query process, as demand space expanded in Algorith m2 Line14, the query terminated time has set already, so the algorith m will not last long or loop over and over again. The time co mp lexity depends on amount of POIs returned in two phases in Algorithm 2 Line 8 and 16, it is i h

(| |+| |)
O . When K=3, LSP has to return 10 POIs to get precise KNN around a user, it is a little more, but the searching time co mplexity is not large. In the other hand, it is a tradeoff between ensuring privacy preserving and query efficiency.

Experime nts

In this section, we discuss 3 main indicators: anonymity success rate, data traffic and average response time. We do experiments on two different data sets to manifest the good performance of our method.

Parameter configurati on

Simu lation experiments are running on Windows 7, CPU is 3.5GHz Intel Core i7 processor and RAM is 16GB. We write the algorith ms with Java, and we use two data sets, one is a real data set fro m Board on Geographical Names 1, denoted as GDS, it includes 358957 PoIs. The other one is simulated data set 2 , denoted as TDS, this data set is generated widely used Thomas Brinkhoff Generator wh ich is based on road networks of Oldenburg in Germany, it generates a city area about 24km×27km. The bandwidth between CS and users is 3Mbps. At LSP end, each data set of POIs is indexed by a 2K bytes R-tree structure. The parameter configurations are shown in the following Table 1 Distance between user and anchor ( , ') dist q q 200 ( , ') 1600 dist q q  1000

Success rate of anchor generating

We run the experiments on both data set GDS and TDS, we d iscuss the success rate of anchor generating when thresholds T X and s  vary in Formu la (4) and Algorith m 2. In Fig. 7, when T X increases, success rate of anchor generating is coming down and keeps stable around 80%, that is due to some p laces with smaller visiting number are not considered sensitive any more, in a valid region, CS is hard to find enough sensitive places around the user. To the same in Fig. 8, when similarity threshold is increasing, the sensitive places around a user must be similar enough to visiting number and visiting time, it means some places will be filtered. So the anchor generating is affected by these factors.

 http://geonames.usgs.gov/index.html  http://iapg.jade-hs.de/personen/brinkhoff/generator/

Compare with S paceTwist

We compares our Algorith m 2 to SpaceTwist on data set GDS and TDS, and mainly d iscuss the communicat ion cost when K and ( , ') dist q q are changing. As shown in Fig. 9-10, when K is increasing, packages are going up on both data set, and Algorithm 2 is than SpaceTwist, especially K varies fro m 11-15, packages are nearly twice than SpaceTwist. That is due to our algorith m expands demand space and continue query until supply space covers it again. LSP has to continue returning POIs until precise KNN POIs are obtained by CS, therefore the communicat ion is increasing, and when K becomes larger, LSP needs to search more area to get enough POIs, packages are even more. Although Algorithm 2 has higher communicat ion, it is much more precise than SpaceTwist, because the POIs found in our algorith m are around a user rather than the anchor, but SpaceTwist's are all around the anchor q', as shown in Fig. 6 ( , ') dist q q varies on GSD Fig. 12. ( , ') dist q q varies on TDS As shown in Fig. 1112, when an anchor is further fro m the user, LSP has to search a large area to get enough POIs, so its communication increases on both data set, as we discuss the anchor generating in our algorithm is not far away fro m a user based on grids, that ensures the communicat ion cost of Algorith m 2 is in a reasonable range, in our experiments, we suppose there is no more than 1000 meters between neighbor grids. Commun ication of Algorith m 2 is higher than SpaceTwist, because it searches a larger area as demand space expands.

For location privacy preserving when a user is in a sensitive area, we propose an anchor generating method using a user's neighbor sensitive places to achieve l-diversity. By filtering places unsatisfied, CS generates an anchor and uses it to replaces a user's actual location in a query. As the anchor locates at an overlap area of several sensitive places, it increases the probability of appearing at different sensitive places for a user, it avoids the leakage of location privacy when a user and her anchor are both in the same sensitive area. In the query phase, CS needn't submit any user's actual location instead of the generated anchor. According to the POIs set returned by LSP, CS can deduce precise K NN POIs around a user, wh ich is much mo re precise than SpaceTwist. Experiments and performance analysis show that our method is better in security and quality aspects, and its complexity and commun ication are in a reasonable range.

At the same t ime we also have some defects such as the factors to define sensitive place are single, we only consider user visiting nu mber and its variation tendency. There is also a defect that the deployment of CS is not discussed, since when a CS is confronting lots of users, the response time may be a bottleneck for the CS. We will focus on these problems in our future works.

Fig. 1 .

 1 Fig.1. Cloaking regions

Fig. 2 .

 2 Fig.2. SpaceTwist processing procedure

  uk loc is an actual location, l is sensitive diversity degree, C and R are her query request content and personal requirement in the query respectively. Definiti on 3: CS sends a piece o f query , of a CS and anchor locis the anchor location which is co mputed and satisfied with location diversity,  is the number of POIs returned fro m LSP each t ime.

Fig. 3 . 4 : 1 {

 341 Fig.3. System architecture

  So we define v isiting weight of a vertex i v :

Fig. 5 .

 5 Fig.5. Diversity zone and anchor generating

Algorithm 1 .W 3 . to the grid as 1 vu

 131 Diversity zone and anchor generating 1. Procedure:CS receives a query request , randomly pick a neighbor grid, denote the vector from i points to the ith neighbor grid 5.

Fig. 6 .

 6 Fig.6. K nearest neighbor PoIs query for a user

Fig. 7 .Fig. 8 .

 78 Fig.7. Threshold T X varys Fig. 8. Threshold s  varys

Fig. 9 .

 9 Fig.9. K varies on GSD Fig. 10. K varies on TDS

  (b) and Fig.6 (e), our algorith m pays a little mo re in communicat ion but earns a lot in service quality. Due to demand space expanding, Algorith m 2 can get precise KNN POIs around a user in nearly 100% success rate.

Fig. 11 .

 11 Fig.11.( , ') dist q q varies on GSD Fig.12. ( , ') dist q q varies on TDS

Table 1 .

 1 : Parameters configuration

	Parameters	Value range	Defaults
	Number of users U	100000	U 	400000	300000
	Threshold of users at a sensitive place T X	100	T  X	1000	200
	Sensitive places similarity threshold s 		01 s  	0.4
	Package capacity of PoIs β	1	 	11	6
	PoIs query number K	1	K 	15	8

Acknowledgements. This research is supported by a grant from National Natural Science Foundation of China (No. 61170241, 61073042), The Fundamental Research Funds for the Central Un iversities (HEUCFZ1105), Specialized Research Fund for the Doctoral Program of Higher Education (No. 20132304110017), Excellent Youth Foundation of Heilongjiang Province in Ch ina (No. JC 201117), Science and Technology Research Project of Heilongjiang Education Depart ment (No. 12513049, NO. 12541788), and this paper is also funded by the International Exchange Program of Harb in Engineering University fo r Innovation-oriented Talents Cultivation.


Jianwei Liao

Guoqiang Xiao

Xiaoyan Liu

Lingyu Zhu

Dynamic Stripe Management Mechanism in Distributed File Systems

Keywords: Distributed/parallel file systems, Re-sizing and re-distributing stripes, Varying stripe size, I/O optimization

This paper presents a novel mechanism to dynamically resize and re-distribute stripes on the storage servers in distributed file systems. To put this mechanism to work, the information about logical I/O access on the client side is piggybacked to physical I/O access on the storage server side, for building the relationship between the logical I/O access and physical I/O access. Moreover, this newly presented mechanism supports varying size of stripes on the storage servers to obtain finer concurrency granularity on accessing to data stripes. As a result, the mapping relationship can be utilized to direct stripe re-sizing and re-distributing on the storage servers dynamically for better system performance. Experimental results show that this stripe management mechanism can reduce I/O response time and boost I/O data throughput significantly for applications with complicated access patterns.

Introduction

The progresses in computation, storage and communication technologies firmly speedup the development of complicated data processing applications that need to deal with big data in distributed computing environments. According to the EMC-IDC Digital Universe 2020 study, the amount of data created, replicated, and consumed in China may grow 24-fold over 2012 and 2020 [START_REF] Gantz | The digital universe in 2020: Big Data, Bigger Digital Shadows, Biggest Growth in the Far East-United States[END_REF]. Thus, one particularly difficult challenge in this context is to find the right approach to store and manage such huge amounts of data in a distributed or parallel computing environment. The traditional centralized client/server model file systems have been proven to be a barrier to scalable performance in distributed computing systems [START_REF] Weil | Dynamic metadata management for petabyte-scale file systems[END_REF]. Therefore, the file system deployed in a distributed computing environment is called a distributed file system, which is always employed to be a backend storage system to offer I/O services for various sorts of data-intensive applications. Actually, the distributed file system leverages multiple distributed I/O devices by striping file data across the I/O nodes, and uses high aggregate bandwidth to meet the growing I/O requirements of distributed scientific applications. In other words, a distributed file system is responsible for distributing files on top of the involved storage devices, as well as managing the created files and their attributes [START_REF] Nieuwejaar | The galley parallel file system[END_REF] and [START_REF] Kunkel | Performance evaluation of the pvfs2 architecture[END_REF].

In general, the method describing the mapping from logical files to a physical layout of bytes on storage servers is called file data distribution function or stripe distribution function. The generally adopted stripe distribution function is able to divide one-dimensional logical files into a set of non-overlapping chunks of data, which are called stripes. To be specific, files are supposed to be separated into many stripes, and then stored on the I/O nodes with certain distribution methods. Normally, the stripes are stored in a round robin manner on data files on the storage nodes [START_REF] Latham | A Next-Generation Parallel File System for Linux Clusters[END_REF], certain advanced distributed file systems, such as GPFS [START_REF] Schmuck | Gpfs: A shared-disk file system for large computing clusters[END_REF], Lustre [START_REF] Schwan | Lustre: Building a file system for 1,000-node clusters[END_REF] and Google file system [START_REF] Ghemawat | The Google file system[END_REF] employ this kind of stripe distribution mechanism. It is well-known that data striping performance is also influenced by the application's I/O behavior, however, stripe distribution does not adjust, even though the distribution goes against application's access modes [START_REF] Liao | Self-tuning optimization on storage servers in parallel file system[END_REF]. For instance, the requirements of continuous media file servers differ from the requirements of scientific applications that needs to process multidimensional data but the traditional distributed file systems treat them without any distinction [START_REF] Medina | A self-tuning disk striping system for parallel input/output[END_REF]. From certain previous studies, it seems that the static distribution mechanism and the fixed stripe size configuration may perform poorly in dealing with a substantial quantity of multi-dimensional data, which may be read/written concurrently by a large number of clients [START_REF] Byna | Parallel i/o prefetching using mpi file caching and i/o signatures[END_REF].

In this paper, we propose a dynamic stripe management mechanism for distributed file systems, which enables varying stripe sizes, and supports stripe re-sizing and re-distributing on the storage servers. As a result, the distributed file systems can adjust stripe sizes and distribute stripes dynamically on the basis of both applications' access patterns and their corresponding disk access patterns, to yield better I/O performance. This mechanism makes the following two contributions:

1. Piggybacking applications' access information to disk access patterns. Applications' logical access information reveals the applications' behavior on the client side, but only the stripe access information on the storage servers shows the real disk operations. In this stripe management mechanism, the logical access information is supposed to be piggybacked with client I/O requests for benefiting to mapping logical access to stripe access, but client file systems do not need to keeping logs for logical access. The mapping relationship can definitely do good to conduct I/O optimization strategies on the storage server sides in the distributed file systems. 2. Re-sizing and re-distributing stripes dynamically on the storage servers. Except for supporting varying size of stripes, the newly proposed mechanism is able to perform dynamic stripe re-sizing and re-distributing on the storage servers, according to the mapping relationship between logical access information and physical access information. This indicates that it can boost I/O data throughput, as well as reduce I/O response time through conducting relevant I/O optimization strategies according to both logical and physical access patterns.

The following paper is organized as follows: Section 2 describes certain background knowledge and related work that aims to improve I/O performance in distributed file systems by employing different I/O optimization strategies. We will demonstrate design details of the mechanism of dynamic stripe management on the storage servers in Section 3. The evaluation methodology and relevant results are illustrated in Section 4. Finally, we conclude this paper in Section 5.

Related Work

For the purpose of yielding attractive I/O performance in the distributed file systems, much current work focuses on I/O optimization strategies for better I/O performance by resorting to keeping and analyzing either logical I/O traces or disk I/O traces. This section discusses some typical approaches, which are mainly sorted as the following two categories: I/O Optimization by using either logical I/O access information or physical I/O access information. T. Madhyastha et al. [START_REF] Madhyastha | Automatic Classification of Input/Output Acess Patterns[END_REF] presented two approaches to reveal various file access patterns and then employ these access patterns to carry out the appropriate caching and prefetching optimization for file systems. The main idea for characterizing access patterns is to use neural networks for short time scales and Hidden Markov models for long time scales. The project IOSig+ allows users to classify the I/O access patterns of an application in two steps: 1) obtain the trace of all the I/O operations of the application from the view point of clients; 2) through the offline analysis on the trace to yield the I/O Signature. Therefore, by using the I/O Signatures, which is the information about logical I/O access patterns, certain optimization on I/O systems, such as data pre-fetching, I/O scheduling, and cost model based data access optimization can be conducted [START_REF] Byna | Parallel i/o prefetching using mpi file caching and i/o signatures[END_REF]. Besides, J. He et al. [START_REF] He | I/O Acceleration with Pattern Detection[END_REF] have explored and classified patterns of I/O within applications, thereby allowing powerful I/O optimization strategies including pattern-aware prefetching to enhance I/O performance.

There are also many studies about the analysis of access patterns on disk I/O traces. Z. Li and Y. Zhou first investigated the block correlation in the storage servers by employing data mine techniques, to benefit to I/O optimization in servers [START_REF] Li | C-Miner: Mining Block Correlations in Storage Systems[END_REF] and [START_REF] Li | Mining Block Correlations to Improve Storage Performance[END_REF]. S. Narayan and J. Chandy [START_REF] Narayan | Trace Based Analysis of File System Effects on Disk I/O[END_REF] researched disk I/O traffics under different workloads and different file systems, and they declared the modeling information about physical I/O operations can contribute to I/O optimization tactics for better system performance [START_REF] Narayan | File System Optimization Using Block Reorganization Techniques[END_REF]. In [START_REF] Hsu | The automatic improvement of locality in storage systems[END_REF], an automatic locality-improving storage has been presented, which automatically reorganizes selected disk blocks based on the dynamic reference stream to boost effective storage performance. After that, DiskSeen has been presented that supports to perform prefetching directly at the level of disk layout [START_REF] Jiang | A Prefetching Scheme Exploiting both Data Layout and Access History on Disk[END_REF]. H. Song et al [START_REF] Song | Server-side I/O coordination for parallel file systems[END_REF] have presented a server-side I/O collection mechanism to coordinate file servers for serving one application at a time to decrease the completion time.

Intelligently setting stripe size in file systems. H. Simitci [START_REF] Simitci | Adaptive Disk Striping for Parallel Input/Output[END_REF] proposed an adaptive mechanism to set the size of striping unit according to the system's state. To be specific, the size of stripes can be determined on the ba-sis of some parameters including the request rate, the request size, the network flow, and disk speed. M. Medina et al. [START_REF] Medina | A self-tuning disk striping system for parallel input/output[END_REF] proposed a self-tuning approach for automatically determining and refining the file system's striping parameters based on application access patterns. In other words, this technique relies on the monitoring of application I/O requests including their size, type, duration and inter-arrival times etc., and then a proper analytic model is used to decide file striping parameters to improve overall file system performance. Therefore, the self-tuning file systems usually operate correspondingly according to the principle that the behavior of the file system must change to match the application. B. Dong et al. [START_REF] Dong | A New File-Specific Stripe Size Selection Method for Highly Concurrent Data Access[END_REF] have proposed an analytic model to evaluate the performance of highly concurrent data access, and then they have described how to apply this model to determine the stripe size of a file. However, this adaptive disk striping approach does not allow change the size of file stripe dynamically and various sizes of stripes belonging to the file.

Besides, Triantafillou and Faloutsos [START_REF] Triantafillou | Overlay striping and optimal parallel I/O for modern applications[END_REF] presented the mechanism of overlay striping, which is a novel data distribution scheme, it stores several copies of a file prior to its use, leveraging a number of different stripe widths. As a result, the relevant replica with the most beneficial stripe width will be accessed. N. Ali et al. have presented a fault-tolerant mechanism to distribute the parity computation for generalized Cartesian data distributions on the storage servers. Actually, in [START_REF] Liao | Self-tuning optimization on storage servers in parallel file system[END_REF], we have proposed a self-tuning storage system that supports stripe movement among storage servers on the fly. But it requires the client file system to record the logical I/O events, and the stripe size is fixed all the time.

It is true that logical access patterns on the application side may affect the I/O performance on the storage server side, that is the reason certain file systems enable self-tuning functionality for determining stripe size and stripe location, according to logical access patterns. On the other hand, only the physical access patterns can disclose the disk behaviors corresponding to logical access. However, the fact is that none of the mentioned techniques and tools support the optimization strategy of supporting dynamic re-sizing and re-distributing stripes by analyzing both logical I/O access patterns and their corresponding physical access patterns in the distributed file systems. Therefore, our work addresses that it is able to build the connection between logical I/O access and physical I/O access; then help the storage servers to re-size and re-distribute the stripes, as well as enable varying size of stripes, for better I/O performance.

Dynamic Re-sizing and Re-distributing stripes

In Section 2, we depicted that a major part of I/O tracing approaches proposed by other researchers focus on the logical I/O access occurred on the client file system side, which might be useful for affirming application's I/O access patterns [START_REF] Byna | Parallel i/o prefetching using mpi file caching and i/o signatures[END_REF]. Nevertheless, without relevant information about physical I/O access, it is difficult to build the connection between the applications and the distributed file system for enhancing the I/O performance significantly through I/O optimization on the storage servers. Therefore, this section describes the details of the way to support varying size of stripes, and then enable dynamic re-sizing and redistributing stripes on the storage servers to advance I/O system's performance.

Piggybacking Logical Access Information to Servers

In this newly presented stripe management mechanism, understanding the mapping relationship between logical access and physical access is a critical precondition to perform I/O optimization. Thus, for storage servers, it is necessary to know the information about client file systems and applications. Although we have proposed a mapping mechanism in our previous work [START_REF] Liao | Self-tuning optimization on storage servers in parallel file system[END_REF], it requires the client file systems to keep the track of logical access information, and then send the tracing logs to the server side. To reduce the overhead resulted by client logging in our previous work, we leverage a piggybacking mechanism, to transfer related information from the client node to the storage servers for contributing to construct the mapping relationship between logical access and physical access. To put it from another angle, the client file system is responsible for keeping extra information about the application, client file system and the logical access information; after that, it piggybacks the extra information with relevant I/O request, and sends them to the corresponding storage server. On the other hand, the storage server is supposed to parse the request to separate piggybacked information and the real I/O request. Apart from forwarding the I/O request to the low level file system, the storage server has to record the disk I/O access with the information about the corresponding logical I/O access.

Briefly speaking, when sending a logical I/O request to the storage server, the client file system piggybacks information about the client file systems and the application. In this way, the storage servers can record disk I/O events with associated client information, which plays a critical role for modeling I/O access relationship, and then directing stripe optimization operations on the storage servers dynamically.

Mapping Access Patterns

As mentioned before, the client information is piggybacked to the storage servers, then the storage servers are possible to record the disk I/O operations accompanying with the information about relevant logical I/O events. Figure 1 strates the structure of each piece of logged information, which is stored on the relevant storage server. The information about logical access includes inode information, file descriptor, offset and requested size. On the other hand, the information about the relevant physical access contains storage server ID, stripe ID, block ID and requested size.

After analyzing the recorded logs for a series of I/O operations, we can easily to obtain the relations between logical access and physical access. Figure 2 illustrates an example case about I/O visualization of both kinds of I/O access information. In the figure, the Read request from Client 1 is reflected to Server 1, so that the two relevant stripes on that server will be accessed sequentially, which may damage access concurrency. In addition, the Write request from Client 2 is separately mapped to Server 2 and Server 3. From the visualization illustration between logical access and physical access, it is not difficult to issue I/O optimization on the storage servers after understanding the shortcomings of the current stripes distribution. For example, the Write request from Client 2 is mapped to Server 2 and Server 3, which indicates that the two stripes should be updated, as well as the replicas corresponding to these two stripes. If this Write request is mapped to only one stripe (merging the involved two stripes), the number of replica synchronization can be reduced to a half. That is why we have done the work to support dynamically performing stripe optimization according to the access patterns.

Re-sizing and Re-distributing Functions

This paper presents a stripe management mechanism that allows varying size of stripes on storage servers on the basis of analysis of the mapping of access patterns. In other words, this newly introduced mechanism makes it possible that the stripes are possible to be re-sized and truncated dynamically for some reason. Figure 3 Because the first read needs to lock the whole stripe stored on SS 2, that means the second write or read request should wait until obtain the lock to that stripe, even though it does not read the contents that requested by the first read request. To overcome this problem, this paper introduces a novel stripe management approach, which supports varying size of stripe units, and enables dynamic resizing, re-distributing the existing stripes. Therefore, the conflicted stripe stored on the SS2 can be divided into 2 stripes, and the first read request does not need to lock the stripe file, which is requested by the second read request. Without doubt, after re-sizing and re-distributing operations, the metadata server should be notified to update relevant metadata, e.g. stripe sizes and stripe locations.

Experiments and Evaluation

Experimental Setup

Experimental Platform One cluster and two LANs are used for conducting the experiments, one active metadata server, 4 storage servers are deployed on the 5 nodes of the cluster. Moreover, for emulating a distributed computing environment, 6 client file systems are installed on a LAN that is connected with the cluster by a 1 GigE Ethernet; another 6 client file systems are installed on another LAN but with same node specifications, which is connected with the cluster by a 100M Ethernet, and both LANs equipped with MPICH2-1.4.1. Table 1 show the specifications of nodes on both of them. Evaluation Counterparts To demonstrate the effectiveness of our proposed dynamic stripe management scheme, we have employed the conventional distributed file system and the self-tuning storage system, as comparison counterparts in our experiments:

-Dynamic Re-sizing and Re-distributing Storage (D2RS). The proposed mechanism has been implemented and applied in a prototype distributed file system, which enables varying stripe sizes and dynamic stripe re-sizing. -Conventional Self-Tuning Storage (CSTS). We implemented a self-tuning storage system in our previous work [START_REF] Liao | Self-tuning optimization on storage servers in parallel file system[END_REF], which supports certain preliminary optimized I/O strategies, such as stripe migration on storage servers, but without piggybacking mechanism and supporting for varying size stripes. As a matter of fact, this work is the most related scheme of our proposed D2RS. -Conventional Storage System (CSS). The storage servers are responsible for all I/O operations normally, and the data stripes are distributed with the normal round-robin pattern. That indicates no I/O tracing and no dynamic stripe re-sizing and stripe re-distributing functionality.

Benchmarks We selected two benchmarks to evaluate our proposed stripe management approach and its comparison counterparts.

-Digital Database for Screening Mammography (DDSM), which is a database of digitized film-screen mammograms with associated ground truth and other information. The purpose of this resource is to provide a large set of mammograms in a digital format that may be used by researchers to emulate medical image processing [START_REF]Digital database for screening mammography[END_REF]. -MADbench2, which is an I/O benchmark derived from a real world application analyzing massive cosmic microwave background radiation in the sky from noisy pixelated datasets from satellites [START_REF][END_REF]. Since MADbench2 performs large, contiguous mixed read and write patterns, it has become a popular and often used benchmark in the parallel I/O community.

Experimental Results: Benefits and Overhead

In this section, we are expected to unveil the overhead brought by the scheme of dynamic re-sizing and re-distributing, as well as the benefits brought by this newly presented stripe management scheme. Thus, the following two sub-sections explore both positive and negative aspects of the proposed scheme respectively.

Improvement on I/O performance We employed the aforementioned two application benchmarks to measure I/O responsiveness and data throughput respectively to show the merits brought by our proposed mechanism. First, we executed DDSM on the three storage systems, and recorded the time required for executing all sub-benchmarks in DDSM. The relevant results are reported in Figure 4, and it is not difficult to know that all sub-benchmarks of DDSM completed with the shortest times while it run on D2RS, because the computation times of the sub-benchmarks are the same, but D2RS caused the least times for I/O processing. For instance, when the sub-benchmark is cancer 08, D2RS yielded more than 30% execution accelerating, compared with CSTS, which means D2RS have better I/O responsiveness while processing multi-dimensional datasets.

Moreover, for the purpose of checking the improvement on data throughput by adopting our proposed mechanism, we run MADbench2 benchmark, and set various number of replicas for each stripe to measure read/write data throughput. Actually, in MADbench2, the function S only writes, the function W both reads and writes, the function C only reads; so that, the sub-benchmarks are denoted as S w, W w, W r, C r to show the different I/O operations in the different functions. Figures 5 shows the experimental results of executing MADbench2 benchmark with Shared and Unique subtype when adopting different configuration of replicas. In all sub-figures, X axis shows the names of sub-benchmarks in MADBench2, while Y axis indicates I/O data rate, and the higher one is better. From the results shown in the figure, we can safely make a conclusion, compared with other two comparison counterparts, D2RS could potentially result in better overall data throughput. Especially, while the number of replicas is becoming larger, the improvement on data throughput is more attractive. This is because re-sizing stripes and creating new independent stripes may reduce the update synchronization overhead caused by write operations. Overhead on Client and Storage Servers After disclosing the positive effects brought by the newly proposed stripe management mechanism, it might be interesting to unveil the negative aspects on I/O performance caused by this mechanism. Table 2 shows the execution time and space overheads for performing stripe re-sizing and re-distributing dynamically on the storage servers, as well as keeping the track of physical I/O access. The results show that this newly proposed mechanism can effectively and practically guide re-sizing and re-distributing stripes on the storage servers for different workloads with acceptable overhead on CPU time and disk space. Because MADbench2 is a typical I/O benchmark to test I/O performance of storage systems, more than 7.4% time overhead on trace analyzing and re-sizing stripes on the storage servers. But, for the compute-intensive DDSM application, our proposed mechanism consumed not much time to yield preferable system performance. Namely, while the workload is DDSM, the time required for keeping disk traces and performing dynamic stripe management is around 3.7% of total processing time. This trend indicates that a major part of processing time can be used to tackle I/O processing; therefore, we can understand that this server-side, dynamic stripe management technique is practical for storage systems in distributed computing environments. Besides, we also recorded the disk space utilized to save the physical I/O traces, which are used to analyze access patterns for conducting potential optimization. The relevant results are reported in the table as well. It is clear that the space used for storing I/O traces is not so much, in contrast to the space used for storing the input and output data required by the benchmarks. For instance, DDSM benchmark deal with more than 60 GB data, but it uses less than 600 MB space for saving I/O trace data.

Concluding Remarks

This paper presents a novel stripe management technique in distributed file systems, in which the stripe size is varying from each other, and the data stripes can be re-sized and re-distributed dynamically according to the access patterns of target applications. The evaluation experiments have illustrated the effectiveness of this newly proposed mechanism, and the attractive experimental results demonstrated that our introduced stripe management mechanism is practical for storage systems in distributed computing environments. As a matter of fact, we have implemented this approach into a prototype distributed file system to verify the feasibility of the idea presented in this paper, it can be not only applied to other traditional distributed file systems, but also parallel file systems, such as the Lustre file system, the Google file system, the GPFS file system, or their extensions, as well.

Fig. 1 .

 1 Fig.1. Logged information about logical access and the corresponding physical access

Fig. 2 .

 2 Fig. 2. Mapping Example of logical I/Os and physical I/Os

Fig. 3 .

 3 Fig. 3. Re-distributing and Re-sizing stripes on the storage servers

Fig. 4 .

 4 Fig. 4. Completion Times for Running DDSM Sampled Volumes

Fig. 5 .

 5 Fig. 5. MADbench2 Experimental Results (MPI, SYNC, 18KPIX, 16BIN)

Table 1 .

 1 Specification of Nodes on the Cluster and the LANs

		Cluster	LANs
	CPU	2xIntel(R) E5410 2.33G Intel(R) E5800 3.20G
	Memory 1x4GB 1066MHz/DDR3 4GB DDR3-SDRAM
	Disk	6x114GB 7200rpm SATA 500GB 7200rpm SATA
	Network Intel 82598EB, 10GbE	1000Mb or 100 Mb
	OS	Ubuntu 13.10	Debian 6.0.4

Table 2 .

 2 Overhead on Dynamic Stripe Management Mechanism

	Benchmarks	Consumed time (%) Space for traces (MB)
	DDSM (Overall)	3.7	588.4
	Madbench (Shared, Non-replica)	7.4	332.7
	Madbench (Unique, Non-replica)	8.6	443.8

Acknowledgment This work was supported partially by "National Natural Science Foundation of China (No. 61303038"), "Natural Science Foundation Project of CQ CSTC (No. CSTC2013JCYJA40050)", and "the Opening Project of State Key Laboratory for Novel Software Technology (No. KFK T201 4B17)".