# Frequent-Pattern-Based Broadcast Scheduling for Conflict Avoidance in Multichannel Data Dissemination Systems

Authors: Chuan-Chi Lai; Yu-De Lin; Chuan-Ming Liu
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

With the popularity of mobile devices, using the traditional client-server model to handle a large number of requests is very challenging. Wireless data broadcasting can be used to provide services to many users at the same time, so reducing the average access time has become a popular research topic. For example, some location-based services (LBS) consider using multiple channels to disseminate information to reduce access time. However, data conflicts may occur when multiple channels are used, where multiple data items associated with the request are broadcasted at about the same time. In this article, we consider the channel switching time and identify the data conflict issue in an on-demand multichannel dissemination system. We model the considered problem as a data broadcast with conflict avoidance (DBCA) problem and prove it is NP-complete. We hence propose the frequent-pattern-based broadcast scheduling (FPBS), which provides a new variant of the frequent pattern tree, FP∗-tree, to schedule the requested data. Using FPBS, the system can avoid data conflicts when assigning data items to time slots in the channels. In the simulation, we discussed two modes of FPBS: online and offline. The results show that, compared with the existing heuristic methods, FPBS can shorten the average access time by 30%.


---

## Body

## 1. Introduction

With advances in wireless communications technologies, mobile devices deeply affect our daily lives, such as notebooks, smart phones, and tablets. Users can easily access various information services, such as online news, traffic information, and stock prices. Recently, wireless data dissemination becomes a popular topic [1–3], which can transmit information to a number of users simultaneously. In comparison with the conventional end-to-end transmission (or client-server) model, wireless data dissemination can make use of wireless network channels to reduce the delivery time for obtaining information. Wireless data broadcasting is well-suited to the location-based services (LBS) in an asymmetric communication environment, where a large number of users are interested in popular information such as news [4], traffic reports [5], and multimedia streams [6, 7].In general, wireless data dissemination can be classified into two modes: push-based and pull-based (on-demand). In push-based wireless data dissemination environments [8–10], data items are disseminated cyclically according to a predefined schedule. In fact, the access pattern of data items may change dynamically, and the broadcast frequency of popular data items may be lower than the broadcast frequency of unpopular data items. Such a case will result in a poor average access latency. In view of this, pull-based wireless data dissemination [11–13] that disseminates data items timely according to the received requests was proposed to overcome the aforementioned drawback. In the pull-based mode, the users first upload their demand information to the server through the uplink channel, and then, the relevant information will be immediately arranged into the broadcasting channels for disseminating data to users. In wireless data dissemination environments, a way of judging the quality of a scheduling approach is to measure the access time of the generated schedule. The access time is a measured time period from starting tuning the channels to obtaining all the requested information. Thus, it is important to have a better broadcasting schedule for shorter access time.


### 1.1. Motivation

In early literature, some conventional works [14–16] focus on how to maximize the bandwidth throughout or minimized the access time in single channel environments. Recently, with the advance on antenna techniques, most of works [17–19] has shifted their focus on the similar issues in multiple channel environments. In general, a multichannel wireless data dissemination system can provide a more network bandwidth and a shorter access time for data dissemination than a single-channel wireless data dissemination system can.However, one new issue, data conflict [20–22], emerges while each client retrieves data items on multiple channels with channel switching in push-based broadcasting environments. Two types of conflicts may occur in multichannel dissemination systems. The first type of conflict is that two required data items are allocated on the same time slot of different channels, so the client cannot download the required data items simultaneously. The second type of conflict occurs if two required data items are allocated on the t and t+1 time slots of different channels, respectively. In such a scenario, the client cannot download both required data items during the time period t,t+1. The 1st conflict type is obvious. The reason of the 2nd conflict type is that switching from any channel to a different channel takes time. A client cannot download data at time slot t+1 from one channel if it was downloading data item from another channel at time slot t, because a time slot is already the smallest unit for data retrieving. Note that a client is allowed to access one channel at one time.Such a data conflict issue makes a client miss its needed data items during the time period for channel switching, thereby leading to a worse access time. On the one hand, some works [20–22] provide some solutions from the client’s point of view. These solutions can make each client schedule itself for retrieving the data items on channels efficiently. On the other hand, only one work [13] provides a server-side scheduling algorithm with consideration of the data conflict issue in on-demand multichannel environments. The provided algorithm considers the associations between data items and requests while allocating data items on multiple channels and this provides a conflict-free schedule.Most broadcast scheduling techniques in on-demand multichannel data dissemination environments do not consider the time requirement for channel switching, thereby leading to data conflicts or long access time. This phenomenon motivates us to propose a more efficient server-side scheduling method with conflict avoidance using frequent pattern mining technique, thereby shortening the average access time.


### 1.2. Contribution

In this study, we discuss how to shorten the average access time on a multichannel wireless data dissemination environment under the data conflict conditions. The contributions of this work are listed as follows:(1)
Identify the data broadcast with conflict avoidance (DBCA) problem in on-demand multichannel wireless data dissemination environments and prove the considered DBCA problem isNP-complete(2)
We propose a heuristic approach, frequent-pattern-based broadcast scheduling (FPBS), for providing an approximate schedule in polynomial time. Inspired by frequent-pattern tree (FP-tree), we suggest a new tree, FP∗-tree, for FPBS to schedule the requested data items with the consideration of channel switching(3)
We analyze the time complexity and average access time of FPBS in both average case and worst case(4)
We verify the performance of FPBS which achieves a shorter average access time in comparison with the existing method, UPF [13]The rest of this paper is organized as follows. Section2 gives the background and reviews related research in the literature. Section 3 defines the DBCA problem and proves that the DBCA problem is NP-complete. Section 4 explains the proposed approach with examples and algorithms in detail. In Section 5, we discuss the time complexity and access time of the proposed approach in worst case. Section 6 presents the experimental simulation results and validates the correctness and effectiveness of the proposed methods in various situations. Finally, we conclude this work in Section 7.


## 1.1. Motivation

In early literature, some conventional works [14–16] focus on how to maximize the bandwidth throughout or minimized the access time in single channel environments. Recently, with the advance on antenna techniques, most of works [17–19] has shifted their focus on the similar issues in multiple channel environments. In general, a multichannel wireless data dissemination system can provide a more network bandwidth and a shorter access time for data dissemination than a single-channel wireless data dissemination system can.However, one new issue, data conflict [20–22], emerges while each client retrieves data items on multiple channels with channel switching in push-based broadcasting environments. Two types of conflicts may occur in multichannel dissemination systems. The first type of conflict is that two required data items are allocated on the same time slot of different channels, so the client cannot download the required data items simultaneously. The second type of conflict occurs if two required data items are allocated on the t and t+1 time slots of different channels, respectively. In such a scenario, the client cannot download both required data items during the time period t,t+1. The 1st conflict type is obvious. The reason of the 2nd conflict type is that switching from any channel to a different channel takes time. A client cannot download data at time slot t+1 from one channel if it was downloading data item from another channel at time slot t, because a time slot is already the smallest unit for data retrieving. Note that a client is allowed to access one channel at one time.Such a data conflict issue makes a client miss its needed data items during the time period for channel switching, thereby leading to a worse access time. On the one hand, some works [20–22] provide some solutions from the client’s point of view. These solutions can make each client schedule itself for retrieving the data items on channels efficiently. On the other hand, only one work [13] provides a server-side scheduling algorithm with consideration of the data conflict issue in on-demand multichannel environments. The provided algorithm considers the associations between data items and requests while allocating data items on multiple channels and this provides a conflict-free schedule.Most broadcast scheduling techniques in on-demand multichannel data dissemination environments do not consider the time requirement for channel switching, thereby leading to data conflicts or long access time. This phenomenon motivates us to propose a more efficient server-side scheduling method with conflict avoidance using frequent pattern mining technique, thereby shortening the average access time.


## 1.2. Contribution

In this study, we discuss how to shorten the average access time on a multichannel wireless data dissemination environment under the data conflict conditions. The contributions of this work are listed as follows:(1)
Identify the data broadcast with conflict avoidance (DBCA) problem in on-demand multichannel wireless data dissemination environments and prove the considered DBCA problem isNP-complete(2)
We propose a heuristic approach, frequent-pattern-based broadcast scheduling (FPBS), for providing an approximate schedule in polynomial time. Inspired by frequent-pattern tree (FP-tree), we suggest a new tree, FP∗-tree, for FPBS to schedule the requested data items with the consideration of channel switching(3)
We analyze the time complexity and average access time of FPBS in both average case and worst case(4)
We verify the performance of FPBS which achieves a shorter average access time in comparison with the existing method, UPF [13]The rest of this paper is organized as follows. Section2 gives the background and reviews related research in the literature. Section 3 defines the DBCA problem and proves that the DBCA problem is NP-complete. Section 4 explains the proposed approach with examples and algorithms in detail. In Section 5, we discuss the time complexity and access time of the proposed approach in worst case. Section 6 presents the experimental simulation results and validates the correctness and effectiveness of the proposed methods in various situations. Finally, we conclude this work in Section 7.


## 2. Related Work

In the multichannel dissemination environments, many related research works focused on data scheduling to improve the access time performance [17, 18] from the perspective of spectrum utilization. Yee et al. [17] proposed a greedy algorithm to find the best way to distribute data items into the channels, allowing users to access requested data in a limited time. Zheng et al. [18] considered the data access frequency, data length, and channel bandwidth into a model and proposed a two-level optimization scheduling algorithm (TOSA) to find an appropriate schedule. They also showed that the schedule of TOSA is approximate to the best average time. Yi et al. [19] proposed a method to allow replicating multiple copies of a data item in a broadcasting channel. If there are multiple copies of a popular data item in the channel, the average access time can be effectively reduced.In addition to the above methods, some works considered the priority of incoming queries and found ways to reduce the access time [12, 14, 15, 23]. Lu et al. [14] proposed some algorithms to schedule data for maximum throughput request selection (MTRS) and minimum latency request ordering (MLRO) problems in a single-channel environment and proved that both problems are NP-hard. Xu et al. [15] proposed a SIN-α algorithm with a set of priority decisions based on the ratio of the length of the expiration time over the amount of information. Lv et al. [23] proved that minimizing access time in the broadcasting scheduling of multi-item requests with deadline constraint in a single-channel environment is an NP-hard problem. The authors provided a profit-based heuristic scheduling algorithm to minimize the request miss rate (or delivery miss rate) considering the access frequency of data. Liu and Su [12] focused on reducing the demand for the loss rate and shortening the access time. Two kinds of algorithms, most popular first heuristic (MPFH) and most popular last heuristic (MPLH), were proposed to solve the problems and they also analyzed differences between the online version (the user demands continuously come in the system, so the scheduling task needs to wait until it starts receiving information of the demands) and offline version (the system already has all the information of demands).Some works had found that the dependency between requested data items may greatly influence the performance of multichannel data broadcasting. Lin and Liu [24] considered the dependencies among data items as a directed acyclic graph (DAG). They proved that finding the best schedule preserving dependencies between each data item is an NP-hard problem and proposed some heuristics for the problem. Qiu et al. [25] proposed a three-layer on-demand data broadcasting (ODDB) system for enhancing the uplink access capacity by introducing a virtual node layer. Each virtual node can merge duplicated requests and help the server reduce huge computational load, there by improve the broadcasting efficiency.Lu et al. [20–22] firstly defined two types of well-known data conflicts in multichannel broadcast applications. They proved the client-side retrieval scheduling problem is NP-hard and provided some client-side data retrieval algorithms for helping clients to retrieve data within multiple channels efficiently. Liu et al. [26] firstly proposed a server-side heuristic data scheduling algorithm, dynamic urgency and productivity (DUP), for on-demand multichannel systems with consideration of the request conflict (or request overlapping) issue and the dependency between requests for scheduling at the request level and giving higher priorities to the requests which are close to their deadlines. Such an approach provided a counteracting effect to the request starvation problem and improved the utilization of broadcasting bandwidth. However, they did not consider two types of data conflicts. He et al. [13] proposed a server-side heuristic scheduling approach, most urgent and popular request First (UPF), with the consideration of two types of data conflicts in on-demand systems. Except for UPF method, the hardness of data scheduling problem considering two types of data conflicts from the server perspective is seldom discussed.The comparisons of the existing works and this paper are summarized in Table1. In this work, we propose a new server-side heuristic scheduling approach for providing a conflict-free multichannel data broadcast service with a better performance on the average access time.Table 1
Comparisons of related works and the proposed method.
Related worksSystem modelCriterionMethodData popularityRequest dependencyChannel switchingData conflict[17–19]On-demandLatencyServer-sideNoNoNoNo[12, 14, 15]On-demandLatencyServer-sideYesNoNoNo[21]Push-basedLatencyClient-sideNoNoYesYes[22]Push-basedThroughputClient-sideNoNoYesYes[23]On-demandRequest miss rateServer-sideYesNoNoNo[24, 25]On-demandLatencyServer-sideNoYesNoNo[26]On-demandLatencyServer-sideYesYesNoNo[13]On-demandRequest miss rateServer-sideYesYesYesYesOur workOn-demandLatencyServer-sideYesYesYesYes


## 3. Problem Description

The length of a broadcasting cycle is an important factor which is normally predefined in the wireless data dissemination applications. Most of existing data scheduling strategies focus on investigating how to efficiently schedule data items in each broadcasting cycle. To validate the performance of a scheduling strategy, average access time (or average latency), is the commonly and widely used metric. If the average access time is shorter, users generally can obtain all the requested data in a shorter time, meaning that the used scheduling strategy is more efficient. In the following subsections, we will describe the considered system model, define the considered scheduling problem, and then prove the hardness of this problem.


### 3.1. System Model

In this work, the considered on-demand multichannel data dissemination system is shown in Figure1 and we only consider the one-hop broadcasting scenario. The considered data dissemination system uses ∣C∣+2 antennas with orthogonal frequency division multiplexing (OFDM) technique [27] to provide ∣C∣ downlink broadcast channels, 1 downlink index channel, and 1 uplink request channel, where C=c1,c2,⋯,c∣C∣ and ∣C∣>1. The downlink index channel and request uplink channel are denoted as cindex and cuplink, respectively. Each user device has two antennas with one for receiving data over the downlink broadcast channels and one for transferring requests via the uplink request channel. We assume that each user device can only access one channel at one time. We assume that all the channels are nonoverlapping, synchronous and discretized into fixed-duration slots. The broadcasting server puts the requests coming from the uplink channel into a buffer with first-come-first-serve (FCFS) strategy and handles all the received requests in a batch manner. In this work, we only focus on the efficiency of (application-layer) data/packet scheduling for users to retrieve the requested data items by accessing the downlink channels.Figure 1
The considered on-demand multichannel wireless data dissemination environment.We assume that all the requested data items are in a datasetD=d1,d2,⋯,dD, where D is the size of D, and the length of a broadcasting cycle is L=D in default. Suppose that there are n queries, Q=q1,q2,⋯,qn, and each query qi requests k data items from the dataset D, where i=1,2,⋯,n and k=1,2,⋯,∣D∣. We let qi=d1i,d2i,⋯,dki and all the data items have the same data size, where dji∈D, j=1,2,⋯,k, and ∪i=1nqi⊆D. Thus, the system has to arrange the requested data items into C broadcasting channels. Note that each time slot on a broadcasting channel can contain at most one data item and data replication is only allowed on different channels. That is, multiple copies of one data item may be placed within a broadcasting cycle. Suppose L is the cycle length, each index It at time slot t records the informations about all the data items in time slot t′ and the corresponding requests of these data items, where t′ is obtained by
(1)t′=t+2modL,ift+2>L,t+2,otherwise.When a client tunes in the channel, it will access the index channel in advance until obtaining information about the first required data item.


### 3.2. Problem Formulation

The considered scheduling problem can be treated as a mappingM that data items associated with all the queries to ∣C∣ broadcasting channels. For each data item dji∈D associated with a query qi∈Q, let posqi,dji=cji,pji be the position of data item dji in the broadcast, where cji is the channel number, 1≤cji≤C, and pji is the location of dji on that channel, 1≤pji≤D. Such a mapping M:Q×D⟶ℕ×ℕ is a 1-to-1 mapping.Since there are multiple channels and each user can only tunes into one broadcasting channel at one time instance, each user may switch channels many times for retrieving all the requested data items on different channels. In general, channel switching is a relatively fast operation (in the microsecond range) [28, 29]. For simplicity, we follow the similar assumptions about channel switching in [22], and each channel switching takes one time slot in the considered data dissemination environment. Figure 2 shows an example of the channel switching. However, channel switching may cause a new problem, data conflict, in multichannel wireless data dissemination systems. For example, if one of requested data items for request qi is placed at the previous, the same, or the later location of a scheduled data item which is also associated with qi on different channels, a data conflict occurs. An example of data conflicts is presented in Figure 3. The data conflict may result in a longer access time and can be defined as Definition 1.Definition 1 (data conflict).
For a queryqi, two requested data items dji and dj′i, 1≤j≠j′≤k, ifcji≠cj′i, the conflict occurs when pji=pj′iorpji−pj′i=1.Figure 2
An example of channel switching, where the data itemsd1i, d2i, and d3i are requested by qi.Figure 3
An example of the data conflict problem.Letlocmini denote the minimum value of all the locations of the data items associated with qi and locMaxi is the maximum value of all the positions of the data items associated with qi. In other words, locmini=min1≤j≤kpji and locMaxi=max1≤j≤kpji. The access time of query qi, accqi, can be defined as ∣locMaxi−locmini∣, while the search starts from the beginning of the broadcasting cycle. The average access time for a mapping M is thus accM=∑i=1naccqi/n.In summary, the problem we want to solve in this work isdata broadcast with conflict avoidance (DBCA) problem which can be defined as follows.Definition 2 (DBCA problem).
Suppose all the notations are defined as above. The DBCA problem is to find a mappingM:Q×D⟶1,⋯,C×1,⋯,L such that
(1)
there is no data conflict for each query in the mapping, i.e., w.r.t. queryqi, for each pair of data items dji and dj′i, 1≤j≠j′≤k, we have ∣pji−pj′i∣>1 when cji≠cj′i; and(2)
the average access time ofM, accM=∑i=1naccqi/n, is minimized.


### 3.3. NP-Completeness

To the best of our knowledge, most of the existing works only considered the schedules without data replication in a broadcasting cycle. They did not discuss and analyze the schedules with conflict avoidance problem on multichannel dissemination environments in detail. Conversely, our proposed approach, FPBS, considers a multichannel dissemination environment which allows replicating data items on different channels of a broadcasting cycle. In such a scenario, we investigate the data conflict problem and propose a new approach to avoid this problem. In this subsection, we will prove DBCA problem isNP-complete.In the definition of DBCA problem, the first objective indicates that the broadcasting schedule avoids the data conflict problem. The second objective is to minimize the average access time. Since the server has no prior knowledge about the coming requests, the process for scheduling the broadcasting is made in an online fashion. We first look at the offline version of the DBCA problem in the following and it refers to conflict-free data broadcasting with minimum average latency (CDBML) problem and define it as below.Definition 3 (CDBML problem).
Instance: There areC data broadcasting channels with cycle length L, a set of D data items D=d1,⋯,dD, and a set of n requests Q=q1,⋯,qn. Each request qi, 1≤i≤n, is associated with k data items, d1i,d2i,⋯,dki, where dji∈D, 1≤j≤k≤D. Any two data items associated with two different requests are different, and every data item needs an unit time ut to be broadcast. Let locmini and locMaxi be the start time and finish time of qi, respectively.
Question: Does there exist a mappingM:Q×D⟶1,⋯,∣C∣×1,⋯,L such that
(1)
For two data itemsdji and dji′ associated with qi, ∣pji−pj′i∣>1 and(2)
the average access time,∑i=1n∣locMaxi−locmini/n∣, is minimizedIn the definition of CDBML problem, the first objective indicates that the broadcasting schedule avoids the data conflict problem. The second objective is to reduce the average access time and all of the data items associated some requestqi should be broadcasting before the end of the broadcasting cycle. Wi is an indication function used to present if a request is served or not. To show further that the CDBML problem is NP-complete, we consider a special case of it, where the number of data items associated with each request is the same and equal to the number of channels. That is, we consider the case k=C. The data items associated with different requests are all different. The following gives the definition of the decision problem for the above special case.Definition 4 (CDBMLρ problem).
Instance: There areC data broadcasting channels with cycle length L, a set of D data items D=d1,⋯,dD, a set of n requests Q=q1,⋯,qn, and an integer h. Each request qi, 1≤i≤n, is associated with C data items, d1i,d2i,⋯,d∣C∣i, where dji∈D, 1≤j≤C≤D. Any two data items associated with two different requests are different, and every data item needs an unit time ut to be broadcast. Let locmini and locMaxi be the start time and finish time of qi, respectively.
Question: Does there exist a mappingM:Q×D⟶1,⋯,C×1,⋯,L such that
(1)
For two data itemsdij and dij′ associated with qi, ∣pji−pj′i∣>1 and(2)
∑i=1naccqi/n≤h, where accqi=locMaxi−locminiTo show that the CDBMLρ problem is NP-complete, we reduce the minimizing mean flow time in unit time open shop (MMUOS) scheduling [30] problem with preemption (O∣pi,j∈0,1;pmtn∣ΣCi) to the CDBMLρ problem. [30] has proved such a problem (O∣pi,j∈0,1;pmtn∣ΣCi) is NP-hard by the reduction from the graph coloring problem, and thus, the CDBML problem is NP-hard. The MMUOS problem is defined as follows.Definition 5 (MMUOS problem).
Instance: Givenm machines, a set of n jobs J=J1,J2,⋯,Jn, a set of O unit operations O=o1,o2,⋯,oO, and an integer T. Each job Ji, 1≤i≤n, consists of m unit operations oij, where oi1,oi2,⋯,oim. The jth operation, 1≤j≤m, has to be processed on the jth machine. Job Ji will be processed in a window defined by a release time ri and a finish time ci.
Question: Does there exist a mappingM:Q×D⟶1,⋯,∣C∣×1,⋯,L such that
(1)
For operationsoij and oij′ in job Ji, Moij≠Moij′ and(2)
∑i=1nCi/n≤T, where Ci=∣ci−ri∣Theorem 6.
The CDBMLρproblem isNP-complete.Proof.
It is easy to see that the CDBMLρ problem is in NP, since validating the existence of an given conflict-free schedule simply needs polynomial time. In order to prove the CDBMLρ problem is NP-hard, a reduction from the MMUOS problem can be made. Suppose that I′ is an instance of the MNUOS problem. A corresponding instance I of the CDBMLρ problem can be constructed from I′ as follows:
(1)
An unit operation time is equal to the unit time slot to broadcasting a data item(2)
Let a jobJi correspond to a request qi, 1≤i≤m and operations oij in Ji be the data item dij associated with qi(3)
Letm machines be the C data broadcasting channels (i.e., m=∣C∣)(4)
LetJi’s release time ri be qi’s start time locmini in the schedule(5)
LetJi’s finish time ci be qi’s finish time locMaxi in the schedule(6)
Let integerT be the integer h in CDBMLρ problem.(7)
Let the unit timeut′ in MMUOS problem be three times of ut in CDBMLρ problem (ut′=3∗ut)
According to the last step of the construction, the first objective of MMUOS problem can be equivalent to the first objective of CDBMLρ problem and the above construction can be done in polynomial time. It is straightforward to show that there is a solution for an instance I′ of the MMUOS problem if and only if there is a solution for the instance I of the CDBMLρ problem since the reduction is a one-to-one mapping for the variables from the MMUOS problem to the CDBMLρ problem. Hence, the CDBMLρ problem is NP-complete.Thus, we can conclude the following theorem.Theorem 7.
The CDBML problem isNP-complete.


## 3.1. System Model

In this work, the considered on-demand multichannel data dissemination system is shown in Figure1 and we only consider the one-hop broadcasting scenario. The considered data dissemination system uses ∣C∣+2 antennas with orthogonal frequency division multiplexing (OFDM) technique [27] to provide ∣C∣ downlink broadcast channels, 1 downlink index channel, and 1 uplink request channel, where C=c1,c2,⋯,c∣C∣ and ∣C∣>1. The downlink index channel and request uplink channel are denoted as cindex and cuplink, respectively. Each user device has two antennas with one for receiving data over the downlink broadcast channels and one for transferring requests via the uplink request channel. We assume that each user device can only access one channel at one time. We assume that all the channels are nonoverlapping, synchronous and discretized into fixed-duration slots. The broadcasting server puts the requests coming from the uplink channel into a buffer with first-come-first-serve (FCFS) strategy and handles all the received requests in a batch manner. In this work, we only focus on the efficiency of (application-layer) data/packet scheduling for users to retrieve the requested data items by accessing the downlink channels.Figure 1
The considered on-demand multichannel wireless data dissemination environment.We assume that all the requested data items are in a datasetD=d1,d2,⋯,dD, where D is the size of D, and the length of a broadcasting cycle is L=D in default. Suppose that there are n queries, Q=q1,q2,⋯,qn, and each query qi requests k data items from the dataset D, where i=1,2,⋯,n and k=1,2,⋯,∣D∣. We let qi=d1i,d2i,⋯,dki and all the data items have the same data size, where dji∈D, j=1,2,⋯,k, and ∪i=1nqi⊆D. Thus, the system has to arrange the requested data items into C broadcasting channels. Note that each time slot on a broadcasting channel can contain at most one data item and data replication is only allowed on different channels. That is, multiple copies of one data item may be placed within a broadcasting cycle. Suppose L is the cycle length, each index It at time slot t records the informations about all the data items in time slot t′ and the corresponding requests of these data items, where t′ is obtained by
(1)t′=t+2modL,ift+2>L,t+2,otherwise.When a client tunes in the channel, it will access the index channel in advance until obtaining information about the first required data item.


## 3.2. Problem Formulation

The considered scheduling problem can be treated as a mappingM that data items associated with all the queries to ∣C∣ broadcasting channels. For each data item dji∈D associated with a query qi∈Q, let posqi,dji=cji,pji be the position of data item dji in the broadcast, where cji is the channel number, 1≤cji≤C, and pji is the location of dji on that channel, 1≤pji≤D. Such a mapping M:Q×D⟶ℕ×ℕ is a 1-to-1 mapping.Since there are multiple channels and each user can only tunes into one broadcasting channel at one time instance, each user may switch channels many times for retrieving all the requested data items on different channels. In general, channel switching is a relatively fast operation (in the microsecond range) [28, 29]. For simplicity, we follow the similar assumptions about channel switching in [22], and each channel switching takes one time slot in the considered data dissemination environment. Figure 2 shows an example of the channel switching. However, channel switching may cause a new problem, data conflict, in multichannel wireless data dissemination systems. For example, if one of requested data items for request qi is placed at the previous, the same, or the later location of a scheduled data item which is also associated with qi on different channels, a data conflict occurs. An example of data conflicts is presented in Figure 3. The data conflict may result in a longer access time and can be defined as Definition 1.Definition 1 (data conflict).
For a queryqi, two requested data items dji and dj′i, 1≤j≠j′≤k, ifcji≠cj′i, the conflict occurs when pji=pj′iorpji−pj′i=1.Figure 2
An example of channel switching, where the data itemsd1i, d2i, and d3i are requested by qi.Figure 3
An example of the data conflict problem.Letlocmini denote the minimum value of all the locations of the data items associated with qi and locMaxi is the maximum value of all the positions of the data items associated with qi. In other words, locmini=min1≤j≤kpji and locMaxi=max1≤j≤kpji. The access time of query qi, accqi, can be defined as ∣locMaxi−locmini∣, while the search starts from the beginning of the broadcasting cycle. The average access time for a mapping M is thus accM=∑i=1naccqi/n.In summary, the problem we want to solve in this work isdata broadcast with conflict avoidance (DBCA) problem which can be defined as follows.Definition 2 (DBCA problem).
Suppose all the notations are defined as above. The DBCA problem is to find a mappingM:Q×D⟶1,⋯,C×1,⋯,L such that
(1)
there is no data conflict for each query in the mapping, i.e., w.r.t. queryqi, for each pair of data items dji and dj′i, 1≤j≠j′≤k, we have ∣pji−pj′i∣>1 when cji≠cj′i; and(2)
the average access time ofM, accM=∑i=1naccqi/n, is minimized.


## 3.3. NP-Completeness

To the best of our knowledge, most of the existing works only considered the schedules without data replication in a broadcasting cycle. They did not discuss and analyze the schedules with conflict avoidance problem on multichannel dissemination environments in detail. Conversely, our proposed approach, FPBS, considers a multichannel dissemination environment which allows replicating data items on different channels of a broadcasting cycle. In such a scenario, we investigate the data conflict problem and propose a new approach to avoid this problem. In this subsection, we will prove DBCA problem isNP-complete.In the definition of DBCA problem, the first objective indicates that the broadcasting schedule avoids the data conflict problem. The second objective is to minimize the average access time. Since the server has no prior knowledge about the coming requests, the process for scheduling the broadcasting is made in an online fashion. We first look at the offline version of the DBCA problem in the following and it refers to conflict-free data broadcasting with minimum average latency (CDBML) problem and define it as below.Definition 3 (CDBML problem).
Instance: There areC data broadcasting channels with cycle length L, a set of D data items D=d1,⋯,dD, and a set of n requests Q=q1,⋯,qn. Each request qi, 1≤i≤n, is associated with k data items, d1i,d2i,⋯,dki, where dji∈D, 1≤j≤k≤D. Any two data items associated with two different requests are different, and every data item needs an unit time ut to be broadcast. Let locmini and locMaxi be the start time and finish time of qi, respectively.
Question: Does there exist a mappingM:Q×D⟶1,⋯,∣C∣×1,⋯,L such that
(1)
For two data itemsdji and dji′ associated with qi, ∣pji−pj′i∣>1 and(2)
the average access time,∑i=1n∣locMaxi−locmini/n∣, is minimizedIn the definition of CDBML problem, the first objective indicates that the broadcasting schedule avoids the data conflict problem. The second objective is to reduce the average access time and all of the data items associated some requestqi should be broadcasting before the end of the broadcasting cycle. Wi is an indication function used to present if a request is served or not. To show further that the CDBML problem is NP-complete, we consider a special case of it, where the number of data items associated with each request is the same and equal to the number of channels. That is, we consider the case k=C. The data items associated with different requests are all different. The following gives the definition of the decision problem for the above special case.Definition 4 (CDBMLρ problem).
Instance: There areC data broadcasting channels with cycle length L, a set of D data items D=d1,⋯,dD, a set of n requests Q=q1,⋯,qn, and an integer h. Each request qi, 1≤i≤n, is associated with C data items, d1i,d2i,⋯,d∣C∣i, where dji∈D, 1≤j≤C≤D. Any two data items associated with two different requests are different, and every data item needs an unit time ut to be broadcast. Let locmini and locMaxi be the start time and finish time of qi, respectively.
Question: Does there exist a mappingM:Q×D⟶1,⋯,C×1,⋯,L such that
(1)
For two data itemsdij and dij′ associated with qi, ∣pji−pj′i∣>1 and(2)
∑i=1naccqi/n≤h, where accqi=locMaxi−locminiTo show that the CDBMLρ problem is NP-complete, we reduce the minimizing mean flow time in unit time open shop (MMUOS) scheduling [30] problem with preemption (O∣pi,j∈0,1;pmtn∣ΣCi) to the CDBMLρ problem. [30] has proved such a problem (O∣pi,j∈0,1;pmtn∣ΣCi) is NP-hard by the reduction from the graph coloring problem, and thus, the CDBML problem is NP-hard. The MMUOS problem is defined as follows.Definition 5 (MMUOS problem).
Instance: Givenm machines, a set of n jobs J=J1,J2,⋯,Jn, a set of O unit operations O=o1,o2,⋯,oO, and an integer T. Each job Ji, 1≤i≤n, consists of m unit operations oij, where oi1,oi2,⋯,oim. The jth operation, 1≤j≤m, has to be processed on the jth machine. Job Ji will be processed in a window defined by a release time ri and a finish time ci.
Question: Does there exist a mappingM:Q×D⟶1,⋯,∣C∣×1,⋯,L such that
(1)
For operationsoij and oij′ in job Ji, Moij≠Moij′ and(2)
∑i=1nCi/n≤T, where Ci=∣ci−ri∣Theorem 6.
The CDBMLρproblem isNP-complete.Proof.
It is easy to see that the CDBMLρ problem is in NP, since validating the existence of an given conflict-free schedule simply needs polynomial time. In order to prove the CDBMLρ problem is NP-hard, a reduction from the MMUOS problem can be made. Suppose that I′ is an instance of the MNUOS problem. A corresponding instance I of the CDBMLρ problem can be constructed from I′ as follows:
(1)
An unit operation time is equal to the unit time slot to broadcasting a data item(2)
Let a jobJi correspond to a request qi, 1≤i≤m and operations oij in Ji be the data item dij associated with qi(3)
Letm machines be the C data broadcasting channels (i.e., m=∣C∣)(4)
LetJi’s release time ri be qi’s start time locmini in the schedule(5)
LetJi’s finish time ci be qi’s finish time locMaxi in the schedule(6)
Let integerT be the integer h in CDBMLρ problem.(7)
Let the unit timeut′ in MMUOS problem be three times of ut in CDBMLρ problem (ut′=3∗ut)
According to the last step of the construction, the first objective of MMUOS problem can be equivalent to the first objective of CDBMLρ problem and the above construction can be done in polynomial time. It is straightforward to show that there is a solution for an instance I′ of the MMUOS problem if and only if there is a solution for the instance I of the CDBMLρ problem since the reduction is a one-to-one mapping for the variables from the MMUOS problem to the CDBMLρ problem. Hence, the CDBMLρ problem is NP-complete.Thus, we can conclude the following theorem.Theorem 7.
The CDBML problem isNP-complete.


## 4. Frequent-Pattern-Based Broadcast Scheduling

In this section, we propose an approach, thefrequent-pattern-based broadcast scheduling (FPBS), to shorten the average access time per user for the DBCA problem. In FPBS, we construct a new tree with the frequent patterns of queries. This tree is named as FP∗-tree. FPBS includes four stages: (1) sorting requested data items, (2) constructing the FP∗-tree’s backbone, (3) constructing the FP∗-tree’s accelerating branches, and (4) schedule mapping. In the following, the proposed method will be introduced with a running example in detail.


### 4.1. Stage 1: Sorting Requested Data Items

We consider a running example which uses two data broadcasting channelsc1, c2 and an additional index channel cindex. The data dissemination server receives five queries q1=d2,d5,d7, q2=d2,d3,d4, q3=d1,d3,d6, q4=d1,d3,d4,d5, and q5=d2,d5,d8 and then derives the access frequency fdj of each data item dj in these queries. After that, the server sorts all the data items in each query according to the descending order of their access frequencies and also derives the statistical average access frequency fqi of each query qi. For example, fq1=fd2+fd5+fd7/∣q1∣=3+3+1/3=2.33. Hence, the final result is presented in Table 2.Table 2
The sorted result of requested data items.
QueryRequested data itemsSorted resultfqiq1d2, d5, d7d2, d5, d72.33q2d2, d3, d4d2, d3, d42.67q3d2, d5, d8d2, d5, d82.33q4d1, d3, d4, d5d3, d5, d1, d42.5q5d1, d3, d6d3, d1, d62The detailed process,FPBS_StatisticAndSortQ, for the first stage is presented in Algorithm 1. Line 2 and Line 3 analyze the received query set Q, derive the statistical information, and save it as a temporary set S. The operations from Line 4 to Line 6 sort every requested data item of each query according to the access frequency of the data item. As the example shown in Table 2, the orders of requested data items in queries q4 and q5 change after the sorting. Line 7 and Line 8, respectively, store the results in two lists, listSortedWithSize and listSortedWithFre, in different orders. Finally, the process returns these two lists at Line 9 for the use in following stages.Algorithm 1:Deriving the statistical information and sorted result.
1. FunctionFPBS_StatisticAndSortQInput: a set of queries (clients) Q;Output: two lists of sorted queries with sorted requested data, listSortedWithSize, listSortedWithFre;2 create a temporary setS⟵ϕ;3.S⟵ StatisticDataFrequency(Q)4for each query q in Qdo;5.  sortRequiredDataByFrequency(q, S)6end;7listSortedWithSize⟵ sortQuerySetByQuerySize(S)8listSortedWithFre⟵ sortQuerySetByAverageFrequency(S)9returnlistSortedWithSize, listSortedWithFre;10end;


### 4.2. Stage 2: Constructing the FP∗-Tree’s Backbone

After deriving some statistical information and the sorting result in Table2, the system starts to create the backbone of a FP∗-tree. In this stage, the system will always select the query which requests the most number of data items to be inserted into the FP∗-tree in advance. If there are multiple queries which request the same number of data items, the system will select the one which has the maximum average access frequency fqi. Thus, the system select q4 as the first query to construct the backbone of a FP∗-tree and the result is shown in Figure 4(a). After adding q4 to the FP∗-tree, the system will update the statistical information of unhandled queries, as shown in Table 3.Figure 4
Constructing the backbone of a FP∗-tree step-by-step: (a) add q4, (b) add q1, (c) add q3, and (d) add q5.
(a)(b)(c)(d)Table 3
Updated result after handlingq4.
QueryUnhandled data itemsItems added in FP∗-tree’s backbonefqiq1d2, d7d52q2d2d3, d43q3d2, d8d52q4∅d3, d5, d1, d40q5d6d3, d11After updating the statistical information, the system will select the next query to handle in the same way. In the previously mentioned, bothq1 and q3 request 2 data items so the system will compare the remaining average access frequencies of q1 and q3 (fq1=2, fq3=2) and both values are the same. Then, the query which comes into the system first will be selected, so q1 becomes the next one in this step. Note that the numbering of q1 is smaller than q3’s and it means that q1 comes into the system earlier. Thus, the handling priority of the remaining queries is q1⟶q3⟶q5. While adding data item d2 into the FP∗-tree, the system needs to consider the relations between d2 and the other queries. In this case, q2 and q3 also request the data item d2. The system then checks the other data items which are in the request list of both queries and have been added into the FP∗-tree. Since the level of d4 is larger than d3’s level, the system will insert d2 as d4’s child. Such a way can avoid increasing the access time of q4 which has been handled. After handling d2, the system handles d7 in the same way and the result of FP∗-tree is shown in Figure 4(b). The system then updates the statistical information which is presented in Table 4.Table 4
Updated result after handlingq1.
QueryUnhandled data itemsItems added in FP∗-tree’s backbonefqiq1∅d5, d2, d70q2∅d3, d4, d20q3d8d5, d21q4∅d3, d5, d1, d40q5d6d3, d11The next query which will be handled isq3. Since there are no other queries relating to the requested data item d8, the system needs to add d8 after d2 according to the order of q3’s requested list. However, d2 is also requested by q1, and thus, d2 already has one branch and the position is occupied by d7. Therefore, d8 can only be scheduled in the level (time slot) after d2 and d7. In this case, the system creates a new branch of d2 and inserts an empty node between d2 and d8. Note that an empty node is a node without saving any data item. After handling q3, the results are shown in Figure 4(c). The last query is q5, and there are no other queries relating to d6. Hence, the system has to add d6 after d1 according to the order of q5’s requested list. However, d1 is also requested by q4, and thus, d6 needs to be scheduled after d4. In this case, the system creates a new branch of d1 and inserts an empty node between d1 and d6. Finally, the construction of FP∗-tree’s backbone is finished and the result is shown in Figure 4(d).Algorithm2 presents two functions for the backbone construction. FPBS_CreateBackboneS describes the main process of an FP∗-tree’s backbone construction and FPBS_AddNodeForBackboneT,Np,d is the function of adding a node during the backbone construction. From Line 3 to Line 5, the operations initialize an empty FP∗-tree T and create a sorted query table Qtable with the derived sorted result in the stage 1. The operations from Line 6 to Line 8 handle each requested data item of the first query in the sorted query set. The first query is the most important and has maximum number of requested data items. As shown as the above example in Figure 4(a), the query q4 is the first to be handled. At Line 9, the remaining information of unhandled queries and data items in the query table Qtable will be updated. From Line 10 to Line 17, the operations continuous inserting the unhandled data items of Qtable into the backbone of T. At Line 13, the operation finds the right position of T’s backbone to insert the unhandled data item with the consideration of query dependency and the order of data items. The operations from Line 21 to Line 35 presents the detailed process of adding a data node to the backbone of T. Note that the operation, T.isOverloadNtemp.slot+1, at Line 26 is used to avoid scheduling data items out of ∣C∣ data broadcasting channels. Figures 4(c) and 4(d) are the running examples for such operations.Algorithm 2: Functions used for the FP∗-tree’s backbone construction.
1:FunctionFPBS_CreateBackboneSInput: a sorted set of queries (clients) S;Output: a basic FP∗-tree T;2:  create a empty FP∗-tree T and the root R of T;3:  setS into a query table Qtable;4:  letq⟵S.first()5:  let a temporary pointerNcurr⟵R;6:for each requested data d in qdo;7:Ncurr⟵FPBS_AddNodeForBackboneT,Ncurr,d;8:end;9:  updateQtable;10:whileQtable contains any unhandled required data do11:qun⟵ the query with the maximum number of unhandled data items in Qtable;12:for each unhandled requested data d′ in qundo;13:Nd_p⟵ find the other queries which also needs data d′ and then choose one of the handled data nodes whose slot is maximum in T14:FPBS_AddNodeForBackboneT,Nd′_p,d′;15:end;16:   updateQtable;17:end;18:returnT;19:end;20:FunctionFPBS_AddNodeForBackboneT,Np,dInput: an FP∗-tree T, the parent node Np, and a new data item d;Output: an added node Nd;21:  create a new nodeNd with data item d22:ifNp has children then23:   create an empty nodeNe;24:Np.addChild(Ne);25:   let a temporary pointerNtemp⟵Ne;26:whileT.isOverload(Ntemp.slot+1) do27:    create an empty nodeNe;28:Np.addChild(Ne);29:Ntemp⟵Ne;30:end;31:Ntemp.addChild(Nd);32:else33:Np.addChild(Nd);34end;35:returnNd;36:end;


### 4.3. Stage 3: Constructing the FP∗-Tree’s Accelerating Branches

After the construction of FP∗-tree’s backbone, the system starts to create the accelerating branches to optimize the schedule. The purpose of constructing the accelerating branch is to increase the chance of each user getting the requested data item earlier after switching channels.In this stage, we propose two different ordering rules,request-number-first and frequency-first, to insert data items in the FP∗-tree’s accelerating branches. The priority of a query for the insertion of FP∗-tree is decided by following values: number of requested data items, average access frequency, and arrival time. With request-number-first rule, the system will select the query which requests the maximum number of data items to handle first. If multiple queries request the maximum number of data items, the system will select the one of them that has the maximum average access frequency. If multiple queries has the maximum average access frequency unfortunately, the system will select the query according to its arrival order. Conversely, with frequency-first rule, the system will first select the query which has the maximum average access frequency. If multiple queries has the maximum average access frequency, the system will select the one of them that requests the maximum number of data items. If multiple queries requests the maximum number of data items unfortunately, the system will select the query according to its arrival order. Note that the construction of the FP∗-tree’s backbone always follows the request-number-first rule in our design. The system can use different rules only when constructing accelerated branches of the FP∗-tree.Since different orders of handling queries and data items make the process constructs different accelerating branches of FP∗-trees, we will compare the performance results of different schedules generated by using different rules. By default, the system uses frequency-first rule to select the query for constructing the FP∗-tree’s accelerating branches. Due to limitations on space and the similar process, we only introduce the proposed approach with frequency-first in detail. In this example, the system follows the frequency-first rule and gets the following handling sequence: q2⟶q4⟶q1⟶q3⟶q5. Note that the value of fqi is shown in Table 2.The system first handles queryq2 and q2’s sorted requested data items are d2, d3, and d4. Hence, the system sequentially schedules d2, d3, and d4. When scheduling d2, the system temporarily inserts d2′ into level (or slot) 1 and the position is a right child of the root. Then, the system searches d2 in the backbone and check whether p2>p2′ and p2−p2′>1 or not. In this case, p2>p2′ and p2−p2′=4>1 is hold, so d2 can be inserted into the position of d2′. For the next requested data item d3, the system inserts d3′ after d2 in the accelerating branch and then checks whether the position is legal or not in the same way. In this case, d3 can be inserted into the position of d3′. For the last requested data item d4 by query q2, the system tries to temporarily insert d4′ after d3 in the accelerating branch. However, the system can find d4 in the backbone that p4−p4′≤1. Thus, d4 can not be inserted into the accelerating branch. After handling q2, the result of FP∗-tree is shown in Figure 5(a).Figure 5
Constructing the accelerating branch of the FP∗-tree step-by-step: (a) add q2, (b) add q1, and (c) add q5.
(a)(b)(c)For the next queryq4, the system will do nothing in the accelerating branch. The reason is that q4 is the first query handled in the backbone and the schedule, d3⟶d5⟶d1⟶d4, has been optimized. Go on the next step, q1 is going to be handled and q1’s requested data items are d2, d5, and d7. Since d2 has been inserted into the accelerating branch, the system skips d2 and tries to insert d5 in this step. According to the order of q1’s requested list, d5 needs to be inserted after d2. In the accelerating branch, node d2 already has a child, so the system creates a new branch of d2, inserts an empty node as d2’s right child, and then add temporary d5′ after the empty node. Since there is no d5 whose p5>p5′ in the backbone, it is legal to insert d5 at the position of d5′. For the last requested data item d7 in q1, d7 is inserted in the same way. The system inserts d7′ after d5 in advance and check whether the backbone contains d7 or not. Since p7>p7′ and p7−p7′=2>1, it is legal to insert d7 at the position of d7′. After handling all the requested data items in q1, the result of FP∗-tree is shown in Figure 5(b)After handlingq1, the system will start to handle q3. The sorted requested data items are d2, d5, and d8. Since d2 has been scheduled at the first slot (level) in the accelerating branch, the system skips d2 in this step. The next data item d5 also has been scheduled in the accelerating branch while handing the previous query q1. Hence, the system only needs to handle d8 for q4. According to the requested list of q4, d8 needs to be inserted at a position that is after d2 and d5. In the accelerating branch, p5>p2 so that d8 will be inserted under the d5. Since d5 already has a branch, the system creates a new branch of d5, inserts an empty node after d5, and tries to inserts a temporary d8′ after the empty node (at p8′=5). However, C=2 and the bandwidth has been occupied by d2 and d6 at slot p8′=5. Then, the system will insert an empty node again and try to add a temporary d8′ at position p8′=6. Then, the system starts to find d8 in the backbone and check whether p8>p8′ and p8−p8′>1 or not. In this case, p8−p8′=1, so it is illegal to place d8 at the position of d8′ and the system removes all the empty nodes after d5 in the accelerating branch. Hence, the final FP∗-tree is shown in Figure 5(c).Algorithm 3: Functions used for the construction of the FP∗-tree’s accelerating branch.
1:FunctionFPBS_CreateAcceleratingBranchT,SInput: an FP∗-tree T and a sorted set of queries (clients) SOutput: a final FP∗-tree T2:  let a temporary pointerNcurr⟵R;3:  create a temporary listlistq and a temporary node Ntemp;4:for each query q in Sdo5:for each requested data d in qdo6:Ntemp⟵FPBS_AddNodeForAcceleratingBranchT,Ncurr,d;7:Ncurr⟵RangeSearchT,Ntemp;8:listq.add Ncurr;9:    ifNcurr.slot >T.slot then10:     delete the path oflistq in T;11:     break;12:end13:end14:listq.clear();15:end16:returnT;17:end18:FunctionFPBS_AddNodeForAcceleratingBranchT,Np,dInput: an FP∗-tree T, the parent node Np, and a new data item dOutput: an added node Nd19:  create a new nodeNd with data item d;20:ifNp has children then21:ifNp has a child Nd′ with dthen22:returnNd′;23:else24:    create an empty nodeNe;25:Np.addChild(Ne);26:    let a temporary pointerNtemp⟵Ne;27:whileT.isOverload(Ntemp.slot+1) do28:     create an empty nodeNe;29:Np.addChild(Ne);30:Ntemp⟵Ne;31:end32:    create a new nodeNd with data item d;33:Ntemp.addChild(Nd);34:end35:else36:   create a new nodeNd with data item d;37:Np.addChild(Nd)38:end39:returnNd;40:end41:FunctionFPBS_RangeSearchT,NpInput: an FP∗-tree T and a search node NdOutput: a result node Nd within the search range42:intNume⟵ the number of Nd’s ancestors which are empty;43:intstartSlot⟵Ntemp.slot −Nume+1;44:intendSlot⟵Ntemp.slot +1;45:fori⟵startSlottoendSlotdo46:if find a node Ntemp that has the same data as Nd does at level i of Tthen47:     delete the path that containsNd and all the empty connected ancestors of Nd;48:returnNtemp;49:end50:end51:returnNd;52:endAlgorithm3 presents the pseudocodes for the functions of accelerating branch construction. FPBS_CreateAcceleratingBranchT,S is the main function for constructing accelerating branch. The process calls the subfunction FPBS_AddNodeForAcceleratingBranchT,Ncurr,d to insert a data item into the accelerating branch of T at Line 6. Such a process is similar to the function FPBS_AddNodeForBackboneT,Np,d in the backbone construction. The operation at Line 7 calls another subfunction FPBS_RangeSearchT,Np to check whether the inserted data item is in the search range (or levels)) or not. The insertion will be illegal if the same data item in the backbone of T locates at one of search levels. If the insertion is illegal, the inserted nodes (including the data item and empty node(s)) will be deleted at Line 47.


### 4.4. Stage 4: Schedule Mapping

After finishing stage III, the system will map every slot (or level) of FP∗-tree into the broadcasting channels using the breadth-first-search (BFS) strategy. The final results are shown in Figure 6. Note that the maximum number of data items in each slot (level) is the number of channels, ∣C∣. The mapping process is described as the operations before Line 24 in Algorithm 4. From Lines 25 to 29, the process schedules the index items in index channel and the result is shown in Figure 6. According to the indexing rule defined in (1), the index I1 records the information about who requests the data items in slot 3 and the index I6 records the similar information corresponding to the data items in slot 1.Figure 6
Mapping FP∗-tree into the broadcasting channels with indexes.Consider the example of Table1, for the request q2=d2,d3,d4, the final schedule in Figure 6 generated by the proposed FPBS shows that the user can retrieve all the requested data items d2, d3 (on c2), and d4 (on c1) within 4 time slots including a channel switching. If there is no accelerating branch, the user needs 5 time slots to retrieve data items d2, d3, and d4 on c1. This result shows that the proposed FP∗-tree can indeed reduce the access time.Algorithm 4: The function used for the schedule mapping
1:FunctionFPBS_ScheduleMappingT,S,∣C∣Input: an FP∗-tree T, a sorted query set S, and the munber of channels ∣C∣Output: a scheduled channel set Schannel and a index channel Ichannel2:  let a listlisthandling⟵T.root.children;3:  let a temporary listlistnext⟵∅;4:  create a data channelSchannel with ∣C∣ data broadcasting channels (or rows);5:  create an index channelIchannel⟵∅;6:inti;7:whilelisthandling is not empty do8:i⟵1; /∗i is used as a pointer to the current channel∗/9:for each node N in listhandlingdo10:ifN is an empty node then11:     break;12:else ifN.parent is an empty node then13:     insertN into Schannel whose slot N.slot is not occupied;14:else15:     insertN into the ith channel;16:end17:ifN is not a leaf node then18:     addN’s children into listnext;19:end20:i⟵i+1;21:end22:   copy every node oflistnext to listhandling;23:listnext.clear();24:end25:forj⟵1 to T.height() do26:fori⟵1 to ∣C∣do27:    UseS to check who requests the data item in the slot determined by (1) and channel Ci of Schannel and then update this information to Ichannelj;28:end29:end30:returnIchannel, Schannel;31:end


## 4.1. Stage 1: Sorting Requested Data Items

We consider a running example which uses two data broadcasting channelsc1, c2 and an additional index channel cindex. The data dissemination server receives five queries q1=d2,d5,d7, q2=d2,d3,d4, q3=d1,d3,d6, q4=d1,d3,d4,d5, and q5=d2,d5,d8 and then derives the access frequency fdj of each data item dj in these queries. After that, the server sorts all the data items in each query according to the descending order of their access frequencies and also derives the statistical average access frequency fqi of each query qi. For example, fq1=fd2+fd5+fd7/∣q1∣=3+3+1/3=2.33. Hence, the final result is presented in Table 2.Table 2
The sorted result of requested data items.
QueryRequested data itemsSorted resultfqiq1d2, d5, d7d2, d5, d72.33q2d2, d3, d4d2, d3, d42.67q3d2, d5, d8d2, d5, d82.33q4d1, d3, d4, d5d3, d5, d1, d42.5q5d1, d3, d6d3, d1, d62The detailed process,FPBS_StatisticAndSortQ, for the first stage is presented in Algorithm 1. Line 2 and Line 3 analyze the received query set Q, derive the statistical information, and save it as a temporary set S. The operations from Line 4 to Line 6 sort every requested data item of each query according to the access frequency of the data item. As the example shown in Table 2, the orders of requested data items in queries q4 and q5 change after the sorting. Line 7 and Line 8, respectively, store the results in two lists, listSortedWithSize and listSortedWithFre, in different orders. Finally, the process returns these two lists at Line 9 for the use in following stages.Algorithm 1:Deriving the statistical information and sorted result.
1. FunctionFPBS_StatisticAndSortQInput: a set of queries (clients) Q;Output: two lists of sorted queries with sorted requested data, listSortedWithSize, listSortedWithFre;2 create a temporary setS⟵ϕ;3.S⟵ StatisticDataFrequency(Q)4for each query q in Qdo;5.  sortRequiredDataByFrequency(q, S)6end;7listSortedWithSize⟵ sortQuerySetByQuerySize(S)8listSortedWithFre⟵ sortQuerySetByAverageFrequency(S)9returnlistSortedWithSize, listSortedWithFre;10end;


## 4.2. Stage 2: Constructing the FP∗-Tree’s Backbone

After deriving some statistical information and the sorting result in Table2, the system starts to create the backbone of a FP∗-tree. In this stage, the system will always select the query which requests the most number of data items to be inserted into the FP∗-tree in advance. If there are multiple queries which request the same number of data items, the system will select the one which has the maximum average access frequency fqi. Thus, the system select q4 as the first query to construct the backbone of a FP∗-tree and the result is shown in Figure 4(a). After adding q4 to the FP∗-tree, the system will update the statistical information of unhandled queries, as shown in Table 3.Figure 4
Constructing the backbone of a FP∗-tree step-by-step: (a) add q4, (b) add q1, (c) add q3, and (d) add q5.
(a)(b)(c)(d)Table 3
Updated result after handlingq4.
QueryUnhandled data itemsItems added in FP∗-tree’s backbonefqiq1d2, d7d52q2d2d3, d43q3d2, d8d52q4∅d3, d5, d1, d40q5d6d3, d11After updating the statistical information, the system will select the next query to handle in the same way. In the previously mentioned, bothq1 and q3 request 2 data items so the system will compare the remaining average access frequencies of q1 and q3 (fq1=2, fq3=2) and both values are the same. Then, the query which comes into the system first will be selected, so q1 becomes the next one in this step. Note that the numbering of q1 is smaller than q3’s and it means that q1 comes into the system earlier. Thus, the handling priority of the remaining queries is q1⟶q3⟶q5. While adding data item d2 into the FP∗-tree, the system needs to consider the relations between d2 and the other queries. In this case, q2 and q3 also request the data item d2. The system then checks the other data items which are in the request list of both queries and have been added into the FP∗-tree. Since the level of d4 is larger than d3’s level, the system will insert d2 as d4’s child. Such a way can avoid increasing the access time of q4 which has been handled. After handling d2, the system handles d7 in the same way and the result of FP∗-tree is shown in Figure 4(b). The system then updates the statistical information which is presented in Table 4.Table 4
Updated result after handlingq1.
QueryUnhandled data itemsItems added in FP∗-tree’s backbonefqiq1∅d5, d2, d70q2∅d3, d4, d20q3d8d5, d21q4∅d3, d5, d1, d40q5d6d3, d11The next query which will be handled isq3. Since there are no other queries relating to the requested data item d8, the system needs to add d8 after d2 according to the order of q3’s requested list. However, d2 is also requested by q1, and thus, d2 already has one branch and the position is occupied by d7. Therefore, d8 can only be scheduled in the level (time slot) after d2 and d7. In this case, the system creates a new branch of d2 and inserts an empty node between d2 and d8. Note that an empty node is a node without saving any data item. After handling q3, the results are shown in Figure 4(c). The last query is q5, and there are no other queries relating to d6. Hence, the system has to add d6 after d1 according to the order of q5’s requested list. However, d1 is also requested by q4, and thus, d6 needs to be scheduled after d4. In this case, the system creates a new branch of d1 and inserts an empty node between d1 and d6. Finally, the construction of FP∗-tree’s backbone is finished and the result is shown in Figure 4(d).Algorithm2 presents two functions for the backbone construction. FPBS_CreateBackboneS describes the main process of an FP∗-tree’s backbone construction and FPBS_AddNodeForBackboneT,Np,d is the function of adding a node during the backbone construction. From Line 3 to Line 5, the operations initialize an empty FP∗-tree T and create a sorted query table Qtable with the derived sorted result in the stage 1. The operations from Line 6 to Line 8 handle each requested data item of the first query in the sorted query set. The first query is the most important and has maximum number of requested data items. As shown as the above example in Figure 4(a), the query q4 is the first to be handled. At Line 9, the remaining information of unhandled queries and data items in the query table Qtable will be updated. From Line 10 to Line 17, the operations continuous inserting the unhandled data items of Qtable into the backbone of T. At Line 13, the operation finds the right position of T’s backbone to insert the unhandled data item with the consideration of query dependency and the order of data items. The operations from Line 21 to Line 35 presents the detailed process of adding a data node to the backbone of T. Note that the operation, T.isOverloadNtemp.slot+1, at Line 26 is used to avoid scheduling data items out of ∣C∣ data broadcasting channels. Figures 4(c) and 4(d) are the running examples for such operations.Algorithm 2: Functions used for the FP∗-tree’s backbone construction.
1:FunctionFPBS_CreateBackboneSInput: a sorted set of queries (clients) S;Output: a basic FP∗-tree T;2:  create a empty FP∗-tree T and the root R of T;3:  setS into a query table Qtable;4:  letq⟵S.first()5:  let a temporary pointerNcurr⟵R;6:for each requested data d in qdo;7:Ncurr⟵FPBS_AddNodeForBackboneT,Ncurr,d;8:end;9:  updateQtable;10:whileQtable contains any unhandled required data do11:qun⟵ the query with the maximum number of unhandled data items in Qtable;12:for each unhandled requested data d′ in qundo;13:Nd_p⟵ find the other queries which also needs data d′ and then choose one of the handled data nodes whose slot is maximum in T14:FPBS_AddNodeForBackboneT,Nd′_p,d′;15:end;16:   updateQtable;17:end;18:returnT;19:end;20:FunctionFPBS_AddNodeForBackboneT,Np,dInput: an FP∗-tree T, the parent node Np, and a new data item d;Output: an added node Nd;21:  create a new nodeNd with data item d22:ifNp has children then23:   create an empty nodeNe;24:Np.addChild(Ne);25:   let a temporary pointerNtemp⟵Ne;26:whileT.isOverload(Ntemp.slot+1) do27:    create an empty nodeNe;28:Np.addChild(Ne);29:Ntemp⟵Ne;30:end;31:Ntemp.addChild(Nd);32:else33:Np.addChild(Nd);34end;35:returnNd;36:end;


## 4.3. Stage 3: Constructing the FP∗-Tree’s Accelerating Branches

After the construction of FP∗-tree’s backbone, the system starts to create the accelerating branches to optimize the schedule. The purpose of constructing the accelerating branch is to increase the chance of each user getting the requested data item earlier after switching channels.In this stage, we propose two different ordering rules,request-number-first and frequency-first, to insert data items in the FP∗-tree’s accelerating branches. The priority of a query for the insertion of FP∗-tree is decided by following values: number of requested data items, average access frequency, and arrival time. With request-number-first rule, the system will select the query which requests the maximum number of data items to handle first. If multiple queries request the maximum number of data items, the system will select the one of them that has the maximum average access frequency. If multiple queries has the maximum average access frequency unfortunately, the system will select the query according to its arrival order. Conversely, with frequency-first rule, the system will first select the query which has the maximum average access frequency. If multiple queries has the maximum average access frequency, the system will select the one of them that requests the maximum number of data items. If multiple queries requests the maximum number of data items unfortunately, the system will select the query according to its arrival order. Note that the construction of the FP∗-tree’s backbone always follows the request-number-first rule in our design. The system can use different rules only when constructing accelerated branches of the FP∗-tree.Since different orders of handling queries and data items make the process constructs different accelerating branches of FP∗-trees, we will compare the performance results of different schedules generated by using different rules. By default, the system uses frequency-first rule to select the query for constructing the FP∗-tree’s accelerating branches. Due to limitations on space and the similar process, we only introduce the proposed approach with frequency-first in detail. In this example, the system follows the frequency-first rule and gets the following handling sequence: q2⟶q4⟶q1⟶q3⟶q5. Note that the value of fqi is shown in Table 2.The system first handles queryq2 and q2’s sorted requested data items are d2, d3, and d4. Hence, the system sequentially schedules d2, d3, and d4. When scheduling d2, the system temporarily inserts d2′ into level (or slot) 1 and the position is a right child of the root. Then, the system searches d2 in the backbone and check whether p2>p2′ and p2−p2′>1 or not. In this case, p2>p2′ and p2−p2′=4>1 is hold, so d2 can be inserted into the position of d2′. For the next requested data item d3, the system inserts d3′ after d2 in the accelerating branch and then checks whether the position is legal or not in the same way. In this case, d3 can be inserted into the position of d3′. For the last requested data item d4 by query q2, the system tries to temporarily insert d4′ after d3 in the accelerating branch. However, the system can find d4 in the backbone that p4−p4′≤1. Thus, d4 can not be inserted into the accelerating branch. After handling q2, the result of FP∗-tree is shown in Figure 5(a).Figure 5
Constructing the accelerating branch of the FP∗-tree step-by-step: (a) add q2, (b) add q1, and (c) add q5.
(a)(b)(c)For the next queryq4, the system will do nothing in the accelerating branch. The reason is that q4 is the first query handled in the backbone and the schedule, d3⟶d5⟶d1⟶d4, has been optimized. Go on the next step, q1 is going to be handled and q1’s requested data items are d2, d5, and d7. Since d2 has been inserted into the accelerating branch, the system skips d2 and tries to insert d5 in this step. According to the order of q1’s requested list, d5 needs to be inserted after d2. In the accelerating branch, node d2 already has a child, so the system creates a new branch of d2, inserts an empty node as d2’s right child, and then add temporary d5′ after the empty node. Since there is no d5 whose p5>p5′ in the backbone, it is legal to insert d5 at the position of d5′. For the last requested data item d7 in q1, d7 is inserted in the same way. The system inserts d7′ after d5 in advance and check whether the backbone contains d7 or not. Since p7>p7′ and p7−p7′=2>1, it is legal to insert d7 at the position of d7′. After handling all the requested data items in q1, the result of FP∗-tree is shown in Figure 5(b)After handlingq1, the system will start to handle q3. The sorted requested data items are d2, d5, and d8. Since d2 has been scheduled at the first slot (level) in the accelerating branch, the system skips d2 in this step. The next data item d5 also has been scheduled in the accelerating branch while handing the previous query q1. Hence, the system only needs to handle d8 for q4. According to the requested list of q4, d8 needs to be inserted at a position that is after d2 and d5. In the accelerating branch, p5>p2 so that d8 will be inserted under the d5. Since d5 already has a branch, the system creates a new branch of d5, inserts an empty node after d5, and tries to inserts a temporary d8′ after the empty node (at p8′=5). However, C=2 and the bandwidth has been occupied by d2 and d6 at slot p8′=5. Then, the system will insert an empty node again and try to add a temporary d8′ at position p8′=6. Then, the system starts to find d8 in the backbone and check whether p8>p8′ and p8−p8′>1 or not. In this case, p8−p8′=1, so it is illegal to place d8 at the position of d8′ and the system removes all the empty nodes after d5 in the accelerating branch. Hence, the final FP∗-tree is shown in Figure 5(c).Algorithm 3: Functions used for the construction of the FP∗-tree’s accelerating branch.
1:FunctionFPBS_CreateAcceleratingBranchT,SInput: an FP∗-tree T and a sorted set of queries (clients) SOutput: a final FP∗-tree T2:  let a temporary pointerNcurr⟵R;3:  create a temporary listlistq and a temporary node Ntemp;4:for each query q in Sdo5:for each requested data d in qdo6:Ntemp⟵FPBS_AddNodeForAcceleratingBranchT,Ncurr,d;7:Ncurr⟵RangeSearchT,Ntemp;8:listq.add Ncurr;9:    ifNcurr.slot >T.slot then10:     delete the path oflistq in T;11:     break;12:end13:end14:listq.clear();15:end16:returnT;17:end18:FunctionFPBS_AddNodeForAcceleratingBranchT,Np,dInput: an FP∗-tree T, the parent node Np, and a new data item dOutput: an added node Nd19:  create a new nodeNd with data item d;20:ifNp has children then21:ifNp has a child Nd′ with dthen22:returnNd′;23:else24:    create an empty nodeNe;25:Np.addChild(Ne);26:    let a temporary pointerNtemp⟵Ne;27:whileT.isOverload(Ntemp.slot+1) do28:     create an empty nodeNe;29:Np.addChild(Ne);30:Ntemp⟵Ne;31:end32:    create a new nodeNd with data item d;33:Ntemp.addChild(Nd);34:end35:else36:   create a new nodeNd with data item d;37:Np.addChild(Nd)38:end39:returnNd;40:end41:FunctionFPBS_RangeSearchT,NpInput: an FP∗-tree T and a search node NdOutput: a result node Nd within the search range42:intNume⟵ the number of Nd’s ancestors which are empty;43:intstartSlot⟵Ntemp.slot −Nume+1;44:intendSlot⟵Ntemp.slot +1;45:fori⟵startSlottoendSlotdo46:if find a node Ntemp that has the same data as Nd does at level i of Tthen47:     delete the path that containsNd and all the empty connected ancestors of Nd;48:returnNtemp;49:end50:end51:returnNd;52:endAlgorithm3 presents the pseudocodes for the functions of accelerating branch construction. FPBS_CreateAcceleratingBranchT,S is the main function for constructing accelerating branch. The process calls the subfunction FPBS_AddNodeForAcceleratingBranchT,Ncurr,d to insert a data item into the accelerating branch of T at Line 6. Such a process is similar to the function FPBS_AddNodeForBackboneT,Np,d in the backbone construction. The operation at Line 7 calls another subfunction FPBS_RangeSearchT,Np to check whether the inserted data item is in the search range (or levels)) or not. The insertion will be illegal if the same data item in the backbone of T locates at one of search levels. If the insertion is illegal, the inserted nodes (including the data item and empty node(s)) will be deleted at Line 47.


## 4.4. Stage 4: Schedule Mapping

After finishing stage III, the system will map every slot (or level) of FP∗-tree into the broadcasting channels using the breadth-first-search (BFS) strategy. The final results are shown in Figure 6. Note that the maximum number of data items in each slot (level) is the number of channels, ∣C∣. The mapping process is described as the operations before Line 24 in Algorithm 4. From Lines 25 to 29, the process schedules the index items in index channel and the result is shown in Figure 6. According to the indexing rule defined in (1), the index I1 records the information about who requests the data items in slot 3 and the index I6 records the similar information corresponding to the data items in slot 1.Figure 6
Mapping FP∗-tree into the broadcasting channels with indexes.Consider the example of Table1, for the request q2=d2,d3,d4, the final schedule in Figure 6 generated by the proposed FPBS shows that the user can retrieve all the requested data items d2, d3 (on c2), and d4 (on c1) within 4 time slots including a channel switching. If there is no accelerating branch, the user needs 5 time slots to retrieve data items d2, d3, and d4 on c1. This result shows that the proposed FP∗-tree can indeed reduce the access time.Algorithm 4: The function used for the schedule mapping
1:FunctionFPBS_ScheduleMappingT,S,∣C∣Input: an FP∗-tree T, a sorted query set S, and the munber of channels ∣C∣Output: a scheduled channel set Schannel and a index channel Ichannel2:  let a listlisthandling⟵T.root.children;3:  let a temporary listlistnext⟵∅;4:  create a data channelSchannel with ∣C∣ data broadcasting channels (or rows);5:  create an index channelIchannel⟵∅;6:inti;7:whilelisthandling is not empty do8:i⟵1; /∗i is used as a pointer to the current channel∗/9:for each node N in listhandlingdo10:ifN is an empty node then11:     break;12:else ifN.parent is an empty node then13:     insertN into Schannel whose slot N.slot is not occupied;14:else15:     insertN into the ith channel;16:end17:ifN is not a leaf node then18:     addN’s children into listnext;19:end20:i⟵i+1;21:end22:   copy every node oflistnext to listhandling;23:listnext.clear();24:end25:forj⟵1 to T.height() do26:fori⟵1 to ∣C∣do27:    UseS to check who requests the data item in the slot determined by (1) and channel Ci of Schannel and then update this information to Ichannelj;28:end29:end30:returnIchannel, Schannel;31:end


## 5. Analysis and Discussion

In this section, we analyze the performance of FPBS in terms oftime complexity, space complexity, and access time.


### 5.1. Time Complexity

Suppose that the notations are defined as above and the FP∗-tree is denoted as T, then, the time complexity of the T’s construction will be Onk. The idea of FP∗-tree design comes up from the FP-tree and only one difference between them is that FP∗-tree needs to add an empty node when creating a new branch except for the root node. In the last stage of the proposed method, schedule mapping needs to maps all the data nodes of T to the broadcasting channels and ∣T∣≤nk, so the time complexity of schedule mapping is also Onk. Due the to nature of the FP∗-tree which is evolved from FP-tree, FPBS costs Onk in both average case and worst case. In summary, FPBS provides a polynomial algorithm for solving the DBCA problem.


### 5.2. Space Complexity

After discussing the time complexity of FPBS, we start to analyze the space complexity of FPBS. In this part, we only consider the temporary space for FPBS process. In the stage 1 of FPBS process, the system uses aOnk size table to store the sorted requests and the statistical information. In the stage 2, the system uses the obtained sorted table to construct the backbone of an FP∗-tree and it also costs Onk space. In the stage 3, the system constructs accelerating branches of the FP∗-tree and it costs Onk′ space, where 1≤k′≤k. In the last stage, the system just maps the FP∗-tree to the channels and only costs O1 additional temporary space for traversing the FP∗-tree. That is, the temporary space complexity during the scheduling process is Onk.


### 5.3. Access Time

In wireless data dissemination environments, access time (or latency) is an important metric for validating the efficiency of scheduling. In FPBS, the system always first selects the request, whose size and average access frequency are maximum, and then schedules it in the backbone of FP∗-tree. We then treat is as the base of schedule. That is, the access time for a request qi can be formulated as Theorem 8.Theorem 8.
Suppose thatFis the maximal frequent item-set in the first-scheduled request,t^is the minimum cost for channel switching, andtwait¯is the average waiting time from tuning into the channel to receiving the first required data item for a request, the access time for a requestqican be expressed as(2)accqi=twait¯+∣qi∣+σ1t^+σ2,ifqi⊆F∨qi∩F=∅,twait¯+∣qi∩F∣+∣qi\F∣+σ1t^+σ2,otherwise,
whereσ1 is the frequency of channel switching and σ2 is the frequency of occupied slot (empty node in the FP∗-tree) skipping.Proof.
With the use of index channel in FPBS, the average waiting time can be reduced efficiently. Ifqi⊆F, it means that all the required data items for qi can be obtained before the end of broadcasting all the data items in F. In such a case, the access time for qi will be twait¯+∣qi∣+σ1t^+σ2, where ∣qi∣+σ1t^+σ2≤∣F∣. If qi∩F=∅ (is equivalent to ∣qi∩F∣=0), it means that qi and F are two disjoint sets. In this case, the data items requested by qi only can be allocated after the first-scheduled maximal frequent item-set, so the access time for qi will be twait¯+∣F∣+∣qi∣+σ1t^+σ2. However, the time ∣F∣ can be merged into the average waiting time twait¯ until accessing the first data item requested by qi. Otherwise, for the case of ∣qi\F∣>0, qi and F are two partially overlapping. It means that some required data items for qi will be scheduled after F. Hence, the access time for qi will be twait¯+∣qi∩F∣+∣qi\F∣+σ1t^+σ2, where ∣qi∩F∣+∣qi\F∣+σ1t^+σ2≥∣F∣.After discussing the general case of access time, we also discuss the worst case in following Theorem9.Theorem 9.
Suppose all the notations are defined as above. The worst case of access time will be(3)accworst=twait¯+⋃i=1nqi.Proof.
In general, the worse case is the scenario that a client access the channels from the first time slot to the last time slot. In other words, the worse access time of FPBS will be the height of the FP∗-tree. According to the design of FPBS approach, the accelerating branches of FP∗-tree is impossible to be longer than the backbone of FP∗-tree. Hence, the height of the FP∗-tree HT will be the height of the backbone, ∣⋃i=1nqi∣. In practice, each client tunes in channel at random time slot, so the access time in worst case accworst will be twait¯+∣⋃i=1nqi∣.In FPBS, each data item is not replicated in the FP∗-tree’s backbone and ∣⋃i=1nqi∣. In this work, we focus on minimizing the average access time and the proposed FPBS approach can effectively shorten the access time of each request using the accelerating branches. In (2), the terms ∣qi∩F∣ and ∣qi\F∣ are uncertain since the relation between request qi and the maximal frequent item-set F is unpredictable. Hence, FPBS focus on minimizing the frequencies of channel switching or occupied slot (empty node in the FP∗-tree) skipping, such as σ1 and σ2 in (2). This problem is solved by FP∗-tree using the accelerating branches in our proposed approach. In other words, FPBS is proposed for effectively make the upper bound of access time be tighter. Thus, the worst case becomes a very rare occurrence.


## 5.1. Time Complexity

Suppose that the notations are defined as above and the FP∗-tree is denoted as T, then, the time complexity of the T’s construction will be Onk. The idea of FP∗-tree design comes up from the FP-tree and only one difference between them is that FP∗-tree needs to add an empty node when creating a new branch except for the root node. In the last stage of the proposed method, schedule mapping needs to maps all the data nodes of T to the broadcasting channels and ∣T∣≤nk, so the time complexity of schedule mapping is also Onk. Due the to nature of the FP∗-tree which is evolved from FP-tree, FPBS costs Onk in both average case and worst case. In summary, FPBS provides a polynomial algorithm for solving the DBCA problem.


## 5.2. Space Complexity

After discussing the time complexity of FPBS, we start to analyze the space complexity of FPBS. In this part, we only consider the temporary space for FPBS process. In the stage 1 of FPBS process, the system uses aOnk size table to store the sorted requests and the statistical information. In the stage 2, the system uses the obtained sorted table to construct the backbone of an FP∗-tree and it also costs Onk space. In the stage 3, the system constructs accelerating branches of the FP∗-tree and it costs Onk′ space, where 1≤k′≤k. In the last stage, the system just maps the FP∗-tree to the channels and only costs O1 additional temporary space for traversing the FP∗-tree. That is, the temporary space complexity during the scheduling process is Onk.


## 5.3. Access Time

In wireless data dissemination environments, access time (or latency) is an important metric for validating the efficiency of scheduling. In FPBS, the system always first selects the request, whose size and average access frequency are maximum, and then schedules it in the backbone of FP∗-tree. We then treat is as the base of schedule. That is, the access time for a request qi can be formulated as Theorem 8.Theorem 8.
Suppose thatFis the maximal frequent item-set in the first-scheduled request,t^is the minimum cost for channel switching, andtwait¯is the average waiting time from tuning into the channel to receiving the first required data item for a request, the access time for a requestqican be expressed as(2)accqi=twait¯+∣qi∣+σ1t^+σ2,ifqi⊆F∨qi∩F=∅,twait¯+∣qi∩F∣+∣qi\F∣+σ1t^+σ2,otherwise,
whereσ1 is the frequency of channel switching and σ2 is the frequency of occupied slot (empty node in the FP∗-tree) skipping.Proof.
With the use of index channel in FPBS, the average waiting time can be reduced efficiently. Ifqi⊆F, it means that all the required data items for qi can be obtained before the end of broadcasting all the data items in F. In such a case, the access time for qi will be twait¯+∣qi∣+σ1t^+σ2, where ∣qi∣+σ1t^+σ2≤∣F∣. If qi∩F=∅ (is equivalent to ∣qi∩F∣=0), it means that qi and F are two disjoint sets. In this case, the data items requested by qi only can be allocated after the first-scheduled maximal frequent item-set, so the access time for qi will be twait¯+∣F∣+∣qi∣+σ1t^+σ2. However, the time ∣F∣ can be merged into the average waiting time twait¯ until accessing the first data item requested by qi. Otherwise, for the case of ∣qi\F∣>0, qi and F are two partially overlapping. It means that some required data items for qi will be scheduled after F. Hence, the access time for qi will be twait¯+∣qi∩F∣+∣qi\F∣+σ1t^+σ2, where ∣qi∩F∣+∣qi\F∣+σ1t^+σ2≥∣F∣.After discussing the general case of access time, we also discuss the worst case in following Theorem9.Theorem 9.
Suppose all the notations are defined as above. The worst case of access time will be(3)accworst=twait¯+⋃i=1nqi.Proof.
In general, the worse case is the scenario that a client access the channels from the first time slot to the last time slot. In other words, the worse access time of FPBS will be the height of the FP∗-tree. According to the design of FPBS approach, the accelerating branches of FP∗-tree is impossible to be longer than the backbone of FP∗-tree. Hence, the height of the FP∗-tree HT will be the height of the backbone, ∣⋃i=1nqi∣. In practice, each client tunes in channel at random time slot, so the access time in worst case accworst will be twait¯+∣⋃i=1nqi∣.In FPBS, each data item is not replicated in the FP∗-tree’s backbone and ∣⋃i=1nqi∣. In this work, we focus on minimizing the average access time and the proposed FPBS approach can effectively shorten the access time of each request using the accelerating branches. In (2), the terms ∣qi∩F∣ and ∣qi\F∣ are uncertain since the relation between request qi and the maximal frequent item-set F is unpredictable. Hence, FPBS focus on minimizing the frequencies of channel switching or occupied slot (empty node in the FP∗-tree) skipping, such as σ1 and σ2 in (2). This problem is solved by FP∗-tree using the accelerating branches in our proposed approach. In other words, FPBS is proposed for effectively make the upper bound of access time be tighter. Thus, the worst case becomes a very rare occurrence.


## 6. Simulation Results

We validate and discuss the performance of FPBS in terms of average access time by running the experimental simulations in different scenarios. The unit of time is a time slot. All the simulations are written in C++ and executed on a Windows 7 server which is equipped with an Intel (R) Core (TM) i7-3770 CPU @ 3.4 GHZ and 12G RAM. We use Quandl databases [31] to extract the U.S stock prices and then use the obtained stock dataset as the input of our simulation.We assume that the maximum number of channels is 10 (∣C∣=2,3,⋯,10) in the simulation. Therefore, we assume that one of the channels is the uplink for receiving the request and the remaining 10 channels are used as the downlink broadcasting channel. The detailed parameters of our simulations are shown in Table 5.Table 5
Simulation parameters.
ParameterDefault valueRange (type)Size of dataset,∣D∣500100, 300, 500, 700, 900Number of users5000—Maximum number of requested data items,qmax102, 4, 6, 8, 10Number of downlink broadcast channels,∣C∣62, 3,⋯, 10Size of buffer3000500, 1000,⋯, 4500In the simulations, FPBS is conducted in online and offline modes. In the online mode, the system will use a buffer to keep the information of queries and request data items. When the buffer becomes full, the system will start to schedule data into the broadcasting channels. The scheduled data items will be removed from the buffer and new user demands are continuously coming in the buffer. It means that the FP∗-tree and schedule may change during the simulation. Conversely, we assume that the system in the offline mode schedules the data after storing all the requested information in the buffer.Note that there are two selecting strategies during scheduling process of FPBS, request-number-first and frequency-first. Request-number-first strategy is to select the query according to the length of its requested data items first and then selecting the query according to its average access frequency if multiple queries request same number of data items. Frequency-first strategy is to select the query according to its average access frequency first and then select the query according to the length of its requested data items if multiple queries have the same average access frequency. Hence, we discuss the above two strategies in online and offline modes, respectively.To the best of our knowledge, none of existing works model the optimal performance of the multi-item request scheduling simultaneously considering the channel switching and dependencies between different requests over multichannel dissemination environments. Only [13] provides a heuristic algorithm, UPF, to discuss the similar problem. This is the reason that we choose UPF as the comparative baseline in the simulations.


### 6.1. Size of Dataset

In the first simulation, we discuss the performance of FPBS with different sizes of dataset in terms of average access time. Note that the size of dataset indicates the number of different data items stored in the dataset. Figure7 shows the results in three different cases if the number of channels ∣C∣=3, ∣C∣=6, and ∣C∣=9, respectively. In the ∣C∣=3 channels environment, as shown in Figure 7(a), UPF can outperform the online FPBS approaches, FPBS-Fre-Online and FPBS-Rn-Online, if the size of dataset, ∣D∣, is smaller than 800. The offline FPBS, FPBS-Fre and FPBS-Rn, can always have a better performance than UPF does in all different sizes of dataset.Figure 7
Effect of the different sizes of dataset with different number of channels: (a)∣C∣=3, (b) ∣C∣=6, and (c) ∣C∣=9.
(a)(b)(c)The results depicted from Figures7(a)–7(c) show that UPF has similar performances in different number of channels environments and the trends of UPF’s average access time are always linear increasing. According to the results in Figures 7(b) and 7(c), we can know that both of online and offline FPBS approaches can outperform UPF in different sizes of datasets when ∣C∣≥6. Additionally, the frequency-first strategy, FPBS-Fre, always has the best performance in different scenarios.


### 6.2. Number of Channels

In this part, we discuss the performance of FPBS in different scenarios that the number of broadcasting channels is set from 2 to 20 and the results are shown in Figure8. The results indicate the existing method, UPF, is not suitable to multiple channel (C≥4) broadcasting environments and UPF cannot dynamically schedule data items with the consideration of each user’s requests. That is to say, in comparison with the proposed approach, UPF can not utilize these channels if C≥4. Figures 8(a) and 8(b) show that UPF has a stable performance in the broadcasting environments with different number of channels when the size of dataset is small (∣D∣≤300). Conversely, the results from Figures 8(c)–8(e) show that the average access time of UPF is unstable and becomes a slightly increasing trend when the size of dataset becomes large (∣D∣≥500). The possible reason for this result is that UPF aims to minimize the request miss rate, not the average access time. There may be a trade-off between minimizing the request miss rate and the average access time.Figure 8
Effect of the different number of channels with different sizes of dataset: (a)∣D∣=100, (b) ∣D∣=300, (c) ∣D∣=500, (d) ∣D∣=700, and (e) ∣D∣=900.
(a)(b)(c)(d)(e)Figures8(a) and 8(b) shows the results of each approach in small dataset. FPBS in the offline mode, FPBS-Fre and FPBS-Rn, can have a better performance since the system consider all the requests while constructing the FP∗-tree. According to the results in Figures 8(c)–8(e), the frequency-first strategies, FPBS-Fre and FPBS-Fre-Online, have better performances than the request-number-first strategies, FPBS-Rn and FPBS-Rn-Online, when the size of dataset becomes large (∣D∣≥500).


### 6.3. Number of Requested Data Items

If the number of requested data items becomes larger, the possibility of data dependency between each query becomes higher. In this subsection, we consider the effect of the different number of requested data items on the average access time. As shown in Figure9, one can observe that all the FPBS-based approaches can outperform UPF when the maximum number of requested data items qmax is smaller than 11. When qmax is 2, all the FPBS-based approaches have similar performances on the average access time. As the value of qmax increases, the average access time in all the FPBS-based approaches also increases linearly.Figure 9
Effect of the different number of requested data items with different sizes of dataset: (a)∣D∣=100, (b) ∣D∣=300, (c) ∣D∣=500, (d) ∣D∣=700, and (e) ∣D∣=900.
(a)(b)(c)(d)(e)According to the result in Figure9, we can know that the frequency-first strategies are better than the request-number-first strategies since the performances of FPBS-Fre and FPBS-Fre-Online are more smoothly increasing than the performances of FPBS-Rn and FPBS-Rn-Online. In addition, FPBS-Fre can has the best performance and its trend is almost parallel to the trend of UPS’s performance.


### 6.4. Buffer Size

In the last simulation, we discuss the effect of the different size of buffer on the average access time for comparing two proposed online approaches, FPBS-Rn-Online and FPBS-Fre-Online. We also consider the trend of performance in some scenarios that the number of channel is, respectively, set to 3, 6, and 9.The result in Figure10 indicates that both FPBS-Rn-Online and FPBS-Fre-Online can have shorter average access time as the size of buffer increases. In an environment providing small number (C=3) of channels, as shown as Figure 10(a), FPBS-Fre-Online can has a slightly better performance than FPBS-Rn-Online does when the buffer can store more than 2500 data items. The results in Figures 10(b) and 10(c) show that FPBS-Fre-Online is much better than FPBS-Rn-Online with different size of buffer when the number of channels increases (C≥6).Figure 10
Effect of the different size of buffer with different number of channels: (a)∣C∣=3, (b) ∣C∣=6, and (c) ∣C∣=9.
(a)(b)(c)


### 6.5. Open Issues

In this subsection, we summarize some remaining issues (or potential challenges) in on-demand multi-channel data dissemination systems as follows:(i)
Hardware constraint: although the minimum costt^ for channel switching is normalized as one time slot in FPBS, it is difficult to implement a broadcasting system that meets this condition due to hardware limitations(ii)
Cross-layer system design: in this paper, we design a server-side data scheduling for serving the multi-item requests. For wireless networks, the time-varying and uncertain nature of wireless channels can be considered in the scheduling. Thus, the server needs a new cross-layer system design to simultaneously access the request information in the application layer and channel information in the physical layer and then schedule data items more efficiently


## 6.1. Size of Dataset

In the first simulation, we discuss the performance of FPBS with different sizes of dataset in terms of average access time. Note that the size of dataset indicates the number of different data items stored in the dataset. Figure7 shows the results in three different cases if the number of channels ∣C∣=3, ∣C∣=6, and ∣C∣=9, respectively. In the ∣C∣=3 channels environment, as shown in Figure 7(a), UPF can outperform the online FPBS approaches, FPBS-Fre-Online and FPBS-Rn-Online, if the size of dataset, ∣D∣, is smaller than 800. The offline FPBS, FPBS-Fre and FPBS-Rn, can always have a better performance than UPF does in all different sizes of dataset.Figure 7
Effect of the different sizes of dataset with different number of channels: (a)∣C∣=3, (b) ∣C∣=6, and (c) ∣C∣=9.
(a)(b)(c)The results depicted from Figures7(a)–7(c) show that UPF has similar performances in different number of channels environments and the trends of UPF’s average access time are always linear increasing. According to the results in Figures 7(b) and 7(c), we can know that both of online and offline FPBS approaches can outperform UPF in different sizes of datasets when ∣C∣≥6. Additionally, the frequency-first strategy, FPBS-Fre, always has the best performance in different scenarios.


## 6.2. Number of Channels

In this part, we discuss the performance of FPBS in different scenarios that the number of broadcasting channels is set from 2 to 20 and the results are shown in Figure8. The results indicate the existing method, UPF, is not suitable to multiple channel (C≥4) broadcasting environments and UPF cannot dynamically schedule data items with the consideration of each user’s requests. That is to say, in comparison with the proposed approach, UPF can not utilize these channels if C≥4. Figures 8(a) and 8(b) show that UPF has a stable performance in the broadcasting environments with different number of channels when the size of dataset is small (∣D∣≤300). Conversely, the results from Figures 8(c)–8(e) show that the average access time of UPF is unstable and becomes a slightly increasing trend when the size of dataset becomes large (∣D∣≥500). The possible reason for this result is that UPF aims to minimize the request miss rate, not the average access time. There may be a trade-off between minimizing the request miss rate and the average access time.Figure 8
Effect of the different number of channels with different sizes of dataset: (a)∣D∣=100, (b) ∣D∣=300, (c) ∣D∣=500, (d) ∣D∣=700, and (e) ∣D∣=900.
(a)(b)(c)(d)(e)Figures8(a) and 8(b) shows the results of each approach in small dataset. FPBS in the offline mode, FPBS-Fre and FPBS-Rn, can have a better performance since the system consider all the requests while constructing the FP∗-tree. According to the results in Figures 8(c)–8(e), the frequency-first strategies, FPBS-Fre and FPBS-Fre-Online, have better performances than the request-number-first strategies, FPBS-Rn and FPBS-Rn-Online, when the size of dataset becomes large (∣D∣≥500).


## 6.3. Number of Requested Data Items

If the number of requested data items becomes larger, the possibility of data dependency between each query becomes higher. In this subsection, we consider the effect of the different number of requested data items on the average access time. As shown in Figure9, one can observe that all the FPBS-based approaches can outperform UPF when the maximum number of requested data items qmax is smaller than 11. When qmax is 2, all the FPBS-based approaches have similar performances on the average access time. As the value of qmax increases, the average access time in all the FPBS-based approaches also increases linearly.Figure 9
Effect of the different number of requested data items with different sizes of dataset: (a)∣D∣=100, (b) ∣D∣=300, (c) ∣D∣=500, (d) ∣D∣=700, and (e) ∣D∣=900.
(a)(b)(c)(d)(e)According to the result in Figure9, we can know that the frequency-first strategies are better than the request-number-first strategies since the performances of FPBS-Fre and FPBS-Fre-Online are more smoothly increasing than the performances of FPBS-Rn and FPBS-Rn-Online. In addition, FPBS-Fre can has the best performance and its trend is almost parallel to the trend of UPS’s performance.


## 6.4. Buffer Size

In the last simulation, we discuss the effect of the different size of buffer on the average access time for comparing two proposed online approaches, FPBS-Rn-Online and FPBS-Fre-Online. We also consider the trend of performance in some scenarios that the number of channel is, respectively, set to 3, 6, and 9.The result in Figure10 indicates that both FPBS-Rn-Online and FPBS-Fre-Online can have shorter average access time as the size of buffer increases. In an environment providing small number (C=3) of channels, as shown as Figure 10(a), FPBS-Fre-Online can has a slightly better performance than FPBS-Rn-Online does when the buffer can store more than 2500 data items. The results in Figures 10(b) and 10(c) show that FPBS-Fre-Online is much better than FPBS-Rn-Online with different size of buffer when the number of channels increases (C≥6).Figure 10
Effect of the different size of buffer with different number of channels: (a)∣C∣=3, (b) ∣C∣=6, and (c) ∣C∣=9.
(a)(b)(c)


## 6.5. Open Issues

In this subsection, we summarize some remaining issues (or potential challenges) in on-demand multi-channel data dissemination systems as follows:(i)
Hardware constraint: although the minimum costt^ for channel switching is normalized as one time slot in FPBS, it is difficult to implement a broadcasting system that meets this condition due to hardware limitations(ii)
Cross-layer system design: in this paper, we design a server-side data scheduling for serving the multi-item requests. For wireless networks, the time-varying and uncertain nature of wireless channels can be considered in the scheduling. Thus, the server needs a new cross-layer system design to simultaneously access the request information in the application layer and channel information in the physical layer and then schedule data items more efficiently


## 7. Conclusion

In this paper, we investigate and formulate an emerging problem, DBCA, in multichannel wireless data dissemination environments. We also prove that the DBCA problem isNP-complete. Then, we present a heuristic scheduling approach, FPBS, to avoid data conflicts on multiple broadcasting channels. In FPBS, we use frequent patterns of requested data items to build a FP∗-tree for extracting the correlation between each received request. Thus, data conflicts can be avoided. During the construction of FP∗-tree’s accelerating branch, adding empty nodes at appropriate positions makes the user client have sufficient time to switch the channel for obtaining the required data. We not only analyze that FPBS can be done in polynomial time but also present the upperbound of access time of a request which is related to size of dataset. According to the simulation results, FPBS is much better than the existing work, UPF, in most of cases.



---

*Source: 1863590-2021-12-14.xml*