JP2000022705A - Broadcast cycle determination method - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To enable a practical time to determine the number of broadcast information and the broadcast cycle that can reduce the waiting time until a client obtains desired information. SOLUTION: A broadcast data selection mechanism 31 sorts each broadcast data from a second database 37 in order of D1, D2, D3,..., Dk (subscript 1,
2, 3,..., K are assigned in ascending order of access rate). F1 (1
The remaining Fi except for the broadcast frequency of D1 in the broadcast cycle T)
(The broadcast frequency of Di in one broadcast cycle T), that is, F
2. The values of F3, F4, F5,..., Fk are all set to “1”. The process of decreasing the value of F1 by '1' is continued until the expected value W of the waiting time becomes minimum. F1, F2, F3, F4, F5,... When the expected value W is minimized.
The sum of the values of Fk is determined to be 1 (total number of slots allocated for transmitting broadcast data D1 to Dk). The total number of slots (T-1) allocated for on-demand data transmission is determined at the same time.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a broadcast cycle determining method applied to an environment in which a client and a server communicate with each other through an asymmetric network.

[0002]

2. Description of the Related Art In an information providing system including a server and a plurality of mobile clients (mobile terminals), when a server performs only a broadcast for periodically transmitting all information (data) to be stored to each mobile terminal, The broadcast cycle becomes longer as the number of stored data is larger. Therefore, even if the broadcast cycle of data that is accessed at a high rate is shortened, the waiting time until each mobile terminal acquires desired data becomes longer as a whole system.

Therefore, a method has been proposed in which data having a high access ratio is periodically transmitted as broadcast data, and the remaining data is transmitted as on-demand data in response to an on-demand request from each mobile terminal. This method reduces the number of data to be broadcast and shortens the broadcast cycle, thereby shortening the waiting time for data acquisition at each mobile terminal, and providing non-broadcast data on demand to send a large amount of data to each mobile terminal. Can be provided.

[0004]

In the above-mentioned broadcast data, the access ratio differs for each broadcast data. Therefore, the broadcast data having a higher access ratio has the number of broadcasts (broadcast frequency) in one broadcast cycle. In order to set a high value, a method called an access ratio proportional method is adopted. In this method, a broadcast band allocated to each of the broadcast data set in one broadcast cycle T (the unit is not represented by time but represented by the number of time slots (slots)), that is, the number of slots 1 is defined by each broadcast. This is a method of allocating each broadcast data according to a high access rate to the data. In other words, by assigning more slots to data with a higher access ratio, the expected value of the waiting time until the mobile terminal acquires data is reduced.

Here, the access ratio proportional method will be described in more detail.

In the above method, one of broadcast data i
The broadcast cycle in the broadcast cycle T is the transmission speed S of the broadcast.
This is a value obtained by dividing T by the product of the number of broadcasts (broadcast frequency) Fi in one broadcast cycle T, and is the same as obtaining Fi. Determining Fi is nothing less than determining how to allocate l slots to k broadcast data (the total number of broadcast data).

Next, the expected value W of the waiting time until each mobile terminal acquires data is determined using the Fi determined as described above.
The expected value Bi of the waiting time of each broadcast data will be described. W is obtained by multiplying the expected value Bi by the access ratio Pi of each broadcast data and the expected value Wo of the waiting time of each on-demand data by the access ratio Pi of each on-demand data. It is obtained as a value obtained by adding the sum of the values. The expected value Bi is a value obtained by dividing one half of one broadcast cycle T by the product of the transmission speed S of the broadcast and the number of broadcasts (broadcast frequency) Fi in one broadcast cycle T. In the above access ratio proportional method, Fi is obtained for all values of l between 0 and T and all values of k between 0 and 1 to calculate the expected value W of the waiting time. From that, the expected value W
Is determined to minimize the broadcast data and the cycle.

Now, there are three broadcast data D1, D2 and D3 (k = 3), and 20 slots (l = 1) for broadcast data transmission.
20) Suppose that the access ratios Pi of D1, D2, and D3 are 0.5, 0.3, and 0.2, respectively. In this case, each Fi (the number of broadcasts (or broadcast frequency) in one broadcast cycle T of D1, D2, and D3) is F1 = 20 × 5 /
10 = 10, F2 = 20 × 3/10 = 6, F3 = 20 × 2
/ 10 = 4.

Here, for simplicity, it is assumed that all data N stored in the server is provided as broadcast data,
Assuming that the transmission speed S of the broadcast is 1, T = 1, all broadcast data k = all data N, and W = 20/2 ×
｛(0.5 / 10) + (0.3 / 10) + (0.2 /
10)｝ = 1.5 is obtained. However, if Fi is not an integer, the fractional part is discarded, and the remaining slots are allocated to the broadcast data with the highest access ratio.

However, in the above-described access ratio proportional method, the obtained expected value W of the waiting time may not always be the minimum value. In other words, in the above method, the optimum value of Fi may not be obtained in some cases. For example, the broadcast frequency F1 of the data D1 is F1 = 9, the broadcast frequency F2 of the data D2 is F2 = 6, and the broadcast frequency F3 of the data D3 is F3 = 5. When the value W is obtained, W = 1.456, which is smaller than 1.5 described above.

In view of the above, in order to find a set of broadcast data and a cycle in which the waiting time is minimized, the expected value W of the waiting time is calculated for all combinations of l, k, and Fi described above. A method for finding a combination in which the expected value W takes the minimum value has been studied. However, according to this method, the number of combinations increases as the number of slots and the number of data increases, so that the calculation cannot be performed in a short time, which is not practical.

[0012] Accordingly, an object of the present invention is to reduce the waiting time until a client obtains desired information in an environment in which the broadcast information and the on-demand information are transmitted in combination. The purpose is to be able to make decisions in a practical time.

[0013]

The broadcast cycle determining method according to the first aspect of the present invention is applied to an environment in which a client and a server communicate with each other through an asymmetric network. Is configured to perform a broadcast-type communication for transmitting a plurality of predetermined broadcast information and an on-demand-type communication for transmitting information according to a request of a client, and simulates a broadcast frequency of each broadcast information in one broadcast cycle. Means for calculating the total value of each broadcast frequency obtained each time the variable is performed and the expected value of the waiting time of the client corresponding thereto, and the broadcast frequency of each broadcast frequency when the expected value is minimized. Means for assigning the total value to the cycle of the broadcast communication and the remainder obtained by subtracting this cycle from one broadcast cycle to the cycle of the on-demand communication.

According to the above configuration, the total value of the respective broadcast frequencies when the expected value is minimized is set as the cycle of the broadcast communication, and the remainder obtained by subtracting this cycle from one broadcast cycle is set as the cycle of the on-demand communication. , Respectively. Therefore, the number of broadcast information and the broadcast cycle that can reduce the waiting time until the client acquires the desired information can be determined in a practical time.

In a preferred embodiment according to the first aspect of the present invention, the calculating means and the allocating means are provided in a server.
For each piece of broadcast information, the priority of the broadcast is determined in advance according to the magnitude of the access ratio from the client. The calculation means makes the broadcast frequency of the broadcast information of the first priority variable and fixes the broadcast frequency of all the remaining broadcast information to 1, and calculates the total value of each broadcast frequency when the expected value is minimized. , The period of the broadcast-type communication. The broadcast frequency of each piece of broadcast information decreases after the determination of the broadcast-type communication cycle, with the broadcast-type communication cycle being the upper limit based on the broadcast priority and the broadcast information having the highest priority being the highest and the priority being lowered. It is decided as follows.

The calculating means determines the mutual broadcast frequency between the broadcast information having a certain priority and the broadcast information one level lower than the broadcast information so that the increase in one broadcast frequency is the decrease in the other broadcast frequency. The expected value is obtained by performing variable adjustment, and the value of the broadcast frequency of the higher-order broadcast information when the expected value is minimized is determined as the broadcast frequency of the broadcast information. When there is broadcast information lower than the above two broadcast information, the broadcast frequency is set to 1
The broadcast frequency of the higher-level broadcast information is obtained in a state in which the broadcast frequency is fixed.
This corresponds to a method of obtaining a suboptimal solution in polynomial time in the field of computer science.

The calculation means calculates the broadcast frequency and the above-mentioned expected value of the waiting time for each number of information while varying the total number of information to be transmitted as broadcast information. Is determined as the total number of broadcast information and the broadcast frequency of each broadcast information. The client is, for example, a plurality of mobile clients.

A broadcast cycle determining method according to a second aspect of the present invention is applied to an environment in which a client and a server communicate through an asymmetric network.
It is configured to perform broadcast-type communication for transmitting a plurality of predetermined pieces of broadcast information and on-demand-type communication for transmitting information in response to a request of a client during one broadcast cycle.
A first step of simulating the broadcast frequency of each piece of broadcast information in a broadcast cycle and calculating a total value of each broadcast frequency obtained each time the change is performed and an expected value of the waiting time of the client corresponding thereto; The sum of the broadcast frequencies when the expected value is minimized is defined as the cycle of the broadcast communication, and this cycle is set to 1
A second step of allocating the remainder obtained by subtracting from the broadcast cycle to the cycle of the on-demand communication.

According to a third aspect of the present invention, there is provided a program medium for transmitting, in an environment where a client and a server communicate over an asymmetric network, a server for transmitting a plurality of predetermined pieces of broadcast information during one broadcast cycle. It is configured to perform type communication and on-demand type communication for transmitting information according to a request of a client, and obtains each time the variable is performed while simulating the broadcast frequency of each broadcast information in one broadcast cycle. Means for calculating the total value of each broadcast frequency and the expected value of the waiting time of the client corresponding thereto, and the total value of each broadcast frequency when the expected value becomes the minimum as the cycle of broadcast-type communication, Means for assigning the remainder obtained by subtracting from one broadcast cycle to the cycle of the on-demand communication, respectively. , Computer readable to carry a computer program for operating a computer as a server and each unit.

[0020]

Embodiments of the present invention will be described below in detail with reference to the drawings.

FIG. 1 is an explanatory diagram showing the overall configuration of an information providing system to which a broadcast cycle determining method according to an embodiment of the present invention is applied.

In the above system, one machine and a plurality of machines communicate through an asymmetric network. As shown in the figure, the system includes a plurality of mobile clients (mobile terminals) 11 to 1n each having a client process, a wireless base station 3, a wired network 5, and a host device (server) having a server process. ) 7.

The server 7 selects a plurality of data (broadcast data) to be broadcast in a predetermined broadcast cycle from information (data) to be stored. Then, the selected data is loaded on the stream, and broadcast-type communication for repeatedly transmitting the data to each of the mobile terminals 11 to 1n through the wired network 5, the wireless base station 3, and the downlink channel 4 is performed. The server 7 receives an on-demand request transmitted from each of the mobile terminals 11 to 1n through the uplink channel 2, the radio base station 3, and the wired network 5, and selects data corresponding to the request from the remaining stored data. I do. Then, put the selected data on the same stream as the above stream,
Each mobile terminal 1 is transmitted through the same communication path as that of the broadcast type communication.
Perform on-demand communication to transmit to 1 to 1n.

Each of the mobile terminals 11 to 1n receives the broadcast data transmitted from the server 7 in the above manner. By transmitting an on-demand request to the server 7 via the communication path, on-demand data corresponding to the request is loaded from the server 7 on the same stream as the broadcast data, and transmitted via the communication path. Each of the mobile terminals 11 to 1n receives the data.

FIG. 2 is a functional block diagram showing the internal configuration of each of the mobile terminals 11 to 1n and the server 7. Since each of the mobile terminals 11 to 1n has the same internal configuration, FIG. 2 shows only the internal configuration of the mobile terminal 11, and in the following description, only the internal configuration of the mobile terminal 11 will be described. The description of the internal structure of 12-1n is omitted.

As shown in FIG. 2, the mobile terminal 11 includes, as functional components, an information receiving mechanism (receiving mechanism) 9, an acquisition request receiving mechanism (receiving mechanism) 11, a determining mechanism 13, and an information selecting mechanism (selecting mechanism). Mechanism) 15, an acquisition request transmission mechanism (transmission mechanism) 17, a communication mechanism 19, and a result display mechanism (display mechanism) 21.

On the other hand, the server 7 has, as functional components,
An information broadcasting mechanism (broadcasting mechanism) 23, a request receiving mechanism (receiving mechanism) 25, an information searching mechanism (searching mechanism) 27, a data mixing mechanism (mixing mechanism) 29, a broadcast data selecting mechanism (selecting mechanism) 31, , An expected value calculation unit (calculation unit) 33. The server 7 stores a database (first DB) for storing information on the access ratio of the above-described broadcast data and on-demand data from the mobile terminal 11 side.
35 and a database (second DB) 37 for storing broadcast data and on-demand data are placed under the management thereof. Here, regarding the method of acquiring the information on the access ratio accumulated in the first DB 35, a method of integrating the on-demand data request from the mobile terminal 11 in the server 7,
Alternatively, there is a method in which the broadcast is stopped every time a predetermined period elapses, and an on-demand request from the mobile terminal 11 is counted in the server 7.

Next, each functional component of the mobile terminal 11 will be described.

The receiving mechanism 9 transmits data (broadcast data) repeatedly transmitted from the server 7 by broadcast communication or data (on-demand data) transmitted by on-demand communication to the above-described wired network 5 and wireless base station 3. And a downlink channel 4 (hereinafter collectively referred to as a network including these and the uplink channel 2). The broadcast data is provided to the selection mechanism 15 and the on-demand data is provided to the transmission mechanism 17, respectively.

The accepting mechanism 11 accepts a data acquisition request (on-demand data request) input to the mobile terminal 11 by a user (not shown), and provides the accepted data acquisition request to the discriminating mechanism 13.

The determination mechanism 13 reads the data acquisition request from the reception mechanism 11 and determines whether or not the data requested to be acquired by the user is being broadcast (ie, whether it is broadcast data or on-demand data). When it is determined that the broadcast is being broadcast, the acquisition request is given to the selection mechanism 15, and when it is determined that the broadcast is not being broadcast, the acquisition request is given to the transmission mechanism 17.

Upon receiving the acquisition request from the discrimination mechanism 13, the selection mechanism 15 selects data (ie, broadcast data) corresponding to the acquisition request from the data being broadcast received by the receiving mechanism 9, The data is displayed on the display mechanism 21
Give to. The selection mechanism 15 determines that the acquisition request is
3, via the transmission mechanism 17, the reception mechanism 9 receives and provides the data corresponding to the acquisition request through the transmission mechanism 17 (that is, on-demand data) to the display mechanism 21.

The transmission mechanism 17 transmits the acquisition request to the server 7 through the communication mechanism 19 and the network when the acquisition request (that is, the request for on-demand data) is given from the determination mechanism 13. The acquisition request is given to the selection mechanism 15. When on-demand data is transmitted from the server 7 to the receiving mechanism 9 through the network in response to the acquisition request,
The data is read from the receiving mechanism 9 and given to the selecting mechanism 15.

The communication mechanism 19 transmits the on-demand request given from the transmission mechanism 17 to the server 7 through the network.
Broadcast data and on-demand data provided by the user are displayed to a user or the like.

Next, each functional component of the server 7 will be described.

When receiving a broadcast stream in which the broadcast data and the on-demand data are mixed from the mixing mechanism 29, the broadcast mechanism 23 transmits the broadcast stream to the mobile terminal 11 through the above-described network.

The accepting mechanism 25 accepts a request for on-demand data transmitted from the mobile terminal 11 through the network, and gives the request to the selecting mechanism 31.

The search mechanism 27 converts broadcast data and on-demand data into second data based on an instruction from the selection mechanism 31.
The search is performed from the DB 37 and the search result is mixed by the mixing mechanism 29.
Give to. Among the instructions from the selection mechanism 31, the instructions related to the broadcast data are given to the search mechanism 27 periodically, and the instructions related to the on-demand data are given to the search mechanism 27 when the mobile terminal 11 requests the on-demand data.

The mixing mechanism 29 mixes the broadcast data and the on-demand data as a result of the search by the search mechanism 27 to form one broadcast stream.
Send to one. Broadcast data is loaded on the stream periodically, and on-demand data is loaded on the stream when there is a request for on-demand data.

The selection mechanism 31 tentatively determines the number of broadcast data and the broadcast cycle (broadcast frequency) for each broadcast data based on the stored data in the first DB 35, and receives the on-demand data from the mobile terminal 11 through the receiving mechanism 25. When there is a request, data corresponding to the request is determined as on-demand data. The selection mechanism 31 is based on the number of broadcast data when the expected value W of the waiting time calculated by the arithmetic unit 33 is minimized and the broadcast cycle of each broadcast data.
The number of broadcast data and the broadcast cycle for each broadcast data are finally determined, and the mixing mechanism 29 is notified to that effect.

The arithmetic unit 33 is built in the selection mechanism 31. Each time the number of broadcast data temporarily determined by the selection mechanism 31 and the broadcast cycle of each broadcast data are notified, the expectation of the waiting time for them is performed. The value W is calculated, and the minimum value of the expected value W is calculated and notified to the selection mechanism 31.

FIG. 3 is a block diagram showing a mixing mechanism 2 in the above-mentioned system for transmitting a combination of broadcast data and on-demand data.
Reference numeral 9 denotes an example of a stream configured by applying the access ratio proportional method under the control of the selection mechanism 31. In this example,
All the accumulated data are A to F, the broadcast data is A to C, and the on-demand data is the remaining D to F,
Eight slots are given as one broadcast cycle T, and it is determined that data A is broadcast twice and data B and C are broadcast once per cycle by an access ratio proportional method.

Returning to FIG. 2, the processing operations of the selection mechanism 31 and the arithmetic section 33 will be described in detail below.

The selection mechanism 31 selects broadcast data from the data stored in the second DB 37 through the search mechanism 27 based on the information on the access ratio from the mobile terminal 11 stored in the first DB 35.

Here, it is assumed that the number of data stored in the second DB 37 is N, and the number of data to be transmitted as broadcast data by broadcast communication is k (0 ≦ k ≦ N).
It is assumed that the number of slots in one broadcast cycle is T, and the number of slots used for transmitting broadcast data in (the number of slots of) one broadcast cycle T is l (0 ≦ k ≦ l ≦ T). In this case, the second
The stored data in the DB 37 is selected as the broadcast data preferentially from the data having the higher access ratio. Therefore, if the value of k is determined, the set of the broadcast data is also determined. It is also assumed that the value of the number of slots T in one broadcasting cycle is appropriately determined in advance. In the example of FIG. 3, N = 6, k = 3, T
= 8 and l = 4.

As preconditions for the calculation of the expected value of the waiting time by the arithmetic unit 33, the size of each data is equal to the size of the slot and is "1", and the occurrence of an information acquisition request and the transmission of on-demand data are waited. Matrix model M / M / 1
Based on Also, the second DB 37 has N
Data is stored, k of them are provided as broadcast data, and the rest are provided as on-demand data. Further, it is also possible that the data is arranged in descending order of the access ratio, that is, the data having the largest access ratio is No. 1 and the data having the smallest access ratio is No. N.

The expected value of the waiting time of the entire system when the broadcast cycle of each data is changed based on the data access ratio is expressed by the following equation (1).
It can be obtained by multiplying the expected value of each waiting time of the on-demand data by the ratio of accessing each data.

[0048]

(Equation 1) In equation (1), W is the expected value of the waiting time, Pi
Is the rate at which broadcast data or on-demand data is accessed, Bi is the expected value of the waiting time of the broadcast data i, and WO is the expected value of the waiting time of the on-demand data.

Next, the expected value of the waiting time of the broadcast data when the broadcast cycle is made variable, that is, the value of Bi can be obtained by the following equation (2).

Bi = (T / 2) × (1 / Fi) × (1 / S) (2) In the equation (2), T is one broadcasting cycle as described above.
The unit is not the time but the number of slots, and Fi is the number of times the broadcast data i is broadcast during one broadcast cycle, that is, the broadcast frequency. In other words, how many slots in one broadcast cycle T are broadcast data i Is assigned to The relationship between Fi and l described above is expressed by the following equation (3).

[0051]

(Equation 2) Further, S is the number of slots broadcasted per unit time, that is, the transmission speed of the broadcast.

Next, the expected value WO of the waiting time of the on-demand data is calculated based on the queue model. The number of on-demand data transmission slots is the number of remaining slots (T-l) obtained by subtracting the total number of slots 1 allocated for broadcast data transmission from the number of slots T in one broadcasting cycle.
It is shown by the following equations (4) and (5).

WO = (1/2) × (ρ / 1−ρ) × (1 / S−Sb) (4)

(Equation 3) In the equations (4) and (5), ρ is the usage rate of the on-demand data transmission slot, Q is the number of requests for on-demand data from the mobile terminal 11 occurring in a unit time, and Sb is the unit. The number of slots of broadcast data per time, that is, S × (1 / T).

Next, the process of determining the broadcast cycle of the broadcast data i will be described.

The broadcast cycle of the broadcast data i can be represented by T / (S × Fi) from the contents described above.
From Fi), determining Fi is the same as determining the broadcast cycle of each broadcast data, and determining Fi determines the method of allocating l slots to k broadcast data. It is clear that this is the case.

In the present embodiment, first, the broadcast data stored in the second DB 37 are sorted in descending order of access rate to D1, D2, D3,..., Dk (subscripts 1, 2,.
3,..., And k are assigned in ascending order of access rate). Next, the remaining Fi except for F1 at this time (Fi is the broadcast frequency of broadcast data i in one broadcast cycle T), that is, F2,
The values of F3, F4, F5,..., Fk are all set to “1”.

Under the above conditions, the process of reducing the value of F1 (ie, the broadcast frequency of the data D1 with the highest access ratio in one broadcast cycle T) by "1" is performed so that the expected value W of the waiting time is minimized. Continue until Then, F1, F2, F3, F4, F5, when the expected value W becomes the minimum,
.., And the sum of the values of Fk is determined to be 1 (that is, the total number of slots allocated for transmitting the broadcast data D1 to Dk). As a result, the total number of slots (T-1) allocated for on-demand data transmission is determined at the same time.

Next, the process of decreasing the value of F1 when the value of l is determined by "1" and the value of F2 (which is "1" when the value of l is determined) are set to "1". The process of gradually increasing the number of times is continued until the expected value W becomes minimum. Then, the value α of F1 when the expected value W becomes the minimum is determined as the value of F1. Next, the process of decreasing the value of F2 when the value of F1 is determined by "1", and the process of increasing the value of F3 (which is "1" when the value of F1 is determined) by "1". This process is continued until the expected value W becomes minimum. Then, the value β of F2 when the expected value W is minimized is determined as the value of F2.

That is, after determining Fj, F1 + F2 + F3 +
.. Under the condition of + Fk = 1 (constant) and the condition of Fj> Fj + 1, Fj is decreased by “1”, Fj + 1 is increased by “1”, and Fj + 1 is set so that the expected value W of the waiting time is minimized. decide.

By going through such a process, F3
The value of .about.Fk will be determined.

According to the above-described process of determining the broadcast cycle, the amount of calculation of the expected value W of the waiting time can be reduced by setting Fi = 1 for the broadcast data Di having a small access ratio. In other words, by calculating the value of l while all the values of F2 to Fk are set to 1, it is easier to calculate all possible combinations of the values of F1 to Fk than to obtain the value of l. The amount of calculation can be greatly reduced. The same applies to the case of determining the values of Fi (that is, F1 to Fk).

In the above-described process of determining the broadcast cycle, the expected value W of the waiting time is reduced by allocating more slots to the broadcast data having a high access ratio, as in the case of the conventional access ratio proportional method. Based on the policy, each Fi is determined so that the expected value W is minimized. Therefore, it is possible to find Fi with a smaller expected value of waiting time W than in the access ratio proportional method.

Next, the process of determining the above-described broadcast cycle will be further described with a specific example.

Now, in the second DB 37, five broadcast data D
It is assumed that 1 to D5 are accumulated and one broadcast cycle T is 20 slots. It is assumed that, out of the five broadcast data D1 to D5, data having the highest access ratio is D1, data having the next highest access ratio is D2, and data having the lowest access ratio is D5.

Under these conditions, first, F1 = 16,
F2 = F3 = F4 = F5 = 1 (hereinafter, for simplicity, 16:
1: 1: 1: 1), and (1)
The expected value W of the waiting time is obtained based on the equation. At this point, S and Sb in equation (4) are equal (that is, the total number of slots allocated for on-demand data transmission is 0).
), The value on the right side of equation (4) becomes infinity (∞).

Next, with the values of F2 to F5 fixed at 1,
While sequentially decreasing the value of F1 to 15, 14, 13, 12, 11, and 10, the expected value W is obtained based on the equation (1) in each case. The above processing operation is executed while the value of W is decreasing. When the value of F1 is set to 9 (that is, when 9: 1: 1: 1: 1), the value of W that has been decreasing has turned to an increase, and when the value of F1 is 10 (that is, 10: 1). : 1: 1: 1: 1) is the minimum value. Therefore, F1 + F2 at this time
The value of + F3 + F4 + F5, that is, 14 is determined as the value of l. Therefore, the value of (T−1), that is, the total number of slots allocated for on-demand data transmission is 20−14 = 6.
It will be decided. Thereafter, the value of WO becomes a fixed value.

Next, with the values of F3 to F5 fixed at 1,
(9: 2: 1: 1: 1), (8: 3: 1: 1: 1),
(7: 4: 1: 1: 1) on the one hand, the value of F1 is reduced by 9, 8, 7,.
The expected value W is obtained based on the equation (1) for each case while increasing the number by 3, 4,.... The above processing operation is executed while the value of W is decreasing. The value of F1 is 6
When the value of F1 is 7 (that is, 7: 4: 1 :), the value of W that has been decreasing has turned to an increase. (When 1: 1) is the minimum value. Therefore, the value of F1 at this time, that is, 7 is determined as the value of F1.

Next, the values of F2, F3, F4 and F5 are determined in the same manner as described above. As described above, more slots are allocated to broadcast data having a high access ratio ( Fj> Fj + 1), so (7: 4: 1: 1: 1) or (7: 4: 1: 1: 1)
3: 2: 1: 1). Here, the expected value W of the combination of (7: 3: 2: 1: 1) is smaller than the expected value W of the combination of (7: 4: 1: 1: 1). Then all Fis are decided.

The above example is for the case where k = 5 (that is, the total number of broadcast data is 5). However, the same processing as described above is performed with 0 ≦ k ≦ N, and each k is determined. The expected value Wk of the waiting time is obtained based on the calculated Fi, and a process of selecting k when Wk is minimized and Fi (i = 1,..., K) at that time is executed.

FIG. 4 is a flow chart showing the processing operation of the selection mechanism 31 and the arithmetic section 33 shown in FIG.

In FIG. 4, first, the number k of broadcast data is set from “0” to a certain value (steps S 41 to S 4).
3). Then, the broadcast data iO having the highest access ratio
The broadcast frequency of the other broadcast data is set to one, and the value of 1 when the expected value W of the waiting time is minimized is determined (step S44). Next, while the value of l is fixed, the value of the broadcast frequency of the broadcast data iO is reduced by one by one, and the value of the broadcast frequency of the broadcast data iO + 1 having the second highest access ratio is increased by one. The value of the broadcast frequency of the broadcast data iO when it becomes the minimum is determined. Thus, the broadcast frequency value of the broadcast data iO + 1 having the second highest access ratio, the broadcast frequency value of the broadcast data iO + 2 having the third highest access ratio, and so on, are the broadcast frequency values of all the broadcast data in order. Is determined (step S45). The value of k is incremented by one, and the processing shown in steps S44 and S45 is repeated (steps S42 and S43 to S45), and k =
When it becomes N (step S43), the value of k when the expected value W is minimized and the broadcast frequency of each broadcast data are selected (step S46).

Next, a comparison result between a calculation example of the expected value of the waiting time by the above-described determination process and a calculation example of the expected value of the waiting time by the conventional method will be described with reference to FIGS.

First, when calculating the expected value W of the waiting time, the length of one broadcast cycle T is set to 20 slots, the total number of requests Q per unit time from the mobile terminal 11 is set to two, It is assumed that the access ratio can be automatically acquired at a certain timing (for example, every minute), and that all data have the same size. It is also assumed that one slot is used to transmit one piece of data, and it takes one second to transmit the data. Further, the processing time of an on-demand request in the server 7 is set to 0.

Next, it is assumed that there is a pattern as shown in FIG. 5 as an access ratio pattern (access pattern). Since the actual access ratio changes depending on the status of the request issued from the mobile terminal side, the pattern shown in FIG. 5 is only an example. Starting with the access pattern shown in FIG. 5, in various access patterns, the combination that minimizes the expected waiting time W was calculated. As a result, a calculation result as shown in FIG. 6 was obtained.

FIG. 6 shows the results of the calculation of the optimum combination of broadcast data, the broadcast frequency Fi of each broadcast data i, and the expected value W (in seconds) of the waiting time, according to the present embodiment. FIG. 9 is a diagram comparing the data obtained by the conventional method and the data obtained by the conventional access ratio proportional method.

From FIG. 6, it is clear that the expected value W of the waiting time calculated according to the present embodiment is shorter than the expected value W of the waiting time calculated by the conventional access ratio proportional method.

In order to confirm the validity of the decision process according to the present embodiment, an optimum decision process is selected from the combination of the decision process according to the present embodiment and all combinations of broadcast data sets and broadcast frequencies for each broadcast data. A desk-top evaluation was performed with the method of selecting a combination (simple method). In this evaluation, it is assumed that the access ratio to each data is in accordance with Zipf's law.

FIG. 7 shows an evaluation set of parameters used for evaluating the expected amount of waiting time calculation according to the present embodiment and the expected amount of waiting time calculation according to the conventional method.

As shown in FIG. 7, of the parameters included in the evaluation sets 1 and 2, the remaining parameters other than the bias of Zipf are the same. That is,
The number of data (the unit is the number) is set from 5 to 100, and the number of data is set to 50 for one cycle (the number of slots). The transmission speed (slot /
) Are both set to 25, and the number of information acquisition requests (pieces / second) is both set to 100. Only for the deviation of Zipf, the evaluation set 1 is set to 2.0 and the evaluation set 2 is set to 1.0.

FIG. 8 shows the results of evaluation of the expected amount of waiting time calculation according to the present embodiment and the expected amount of waiting time calculation according to the conventional simple method using the evaluation set of FIG. Show.

In FIG. 8, the curve shows the amount of calculation of the expected value W by the conventional simple method, and the curve shows the worst value of the amount of calculation of the expected value W in the present embodiment. The curve shows the amount of calculation of the expected value W in the present embodiment when the bias of Zipf is 2.0.
Expected value W in this embodiment when the deviation of f is 1.0
Shows the calculation amount of.

As shown in FIG. 8, the calculation amount of the expected value W according to the present embodiment is the expected value calculation amount W according to the conventional simple method.
It can be seen that it is reduced to about 1/100 to 1/1000 as compared with FIG. In addition, in the present embodiment, the upper limit of the required amount of calculation (that is, the worst value) is 1
It can also be seen that it is about / 10.

As described above, according to the embodiment of the present invention, the waiting time shorter than the expected value W of the waiting time until the mobile terminals 11 to 1n obtain data obtained by the conventional method is reduced. The expected value W of time can be obtained. When the server 7 calculates the expected value W of the waiting time,
The amount of calculation for a combination of the number of broadcast data, the total number of slots for transmitting broadcast data, and the broadcast cycle of each data can be suppressed to a practical range.

Note that the above-described content relates to one embodiment of the present invention, and does not mean that the present invention is limited to only the above-described content.

[0085]

As described above, according to the present invention,
In an environment in which broadcast information and on-demand information are transmitted in combination, the number and broadcast cycle of the broadcast information that can reduce the waiting time until the client obtains the desired information,
It can be determined in a practical time.

[Brief description of the drawings]

FIG. 1 is an explanatory diagram showing an overall configuration of an information providing system to which a broadcast cycle determining method according to an embodiment of the present invention is applied.

FIG. 2 is a functional block diagram showing an internal configuration of a mobile terminal and a server.

FIG. 3 is an explanatory diagram showing an example of a broadcast stream configured by mixing broadcast data and on-demand data.

FIG. 4 is a flowchart showing a processing operation of a broadcast data selection mechanism and an expected value calculation unit shown in FIG. 3;

FIG. 5 is an explanatory diagram showing an example of a pattern of an access ratio to broadcast data.

FIG. 6 is an explanatory diagram comparing a calculation result according to an embodiment regarding an expected value of a waiting time with a calculation result according to a conventional method.

FIG. 7 shows an expected value calculation amount of a waiting time according to an embodiment;
FIG. 7 is an explanatory diagram showing an evaluation set of parameters used for evaluation with respect to an expected value calculation amount of a waiting time according to a conventional method.

FIG. 8 is an explanatory diagram showing the results of evaluating the expected amount of waiting time calculation according to one embodiment and the expected amount of waiting time calculation according to the conventional method using the evaluation set of FIG. 7;

[Explanation of symbols]

11-1n mobile client (mobile terminal) 2 uplink channel 3 radio base station 4 downlink channel 5 wired network 7 host device (server) 9 information receiving mechanism (receiving mechanism) 11 acquisition request receiving mechanism (receiving mechanism) 13 discriminating mechanism 15 information Selection mechanism (selection mechanism) 17 Acquisition request transmission mechanism (transmission mechanism) 19 Communication mechanism 21 Result display mechanism (display mechanism) 23 Information broadcasting mechanism (broadcasting mechanism) 25 Request reception mechanism (reception mechanism) 27 Information search mechanism (search mechanism) 29 data mixing mechanism (mixing mechanism) 31 broadcast data selection mechanism (selection mechanism) 33 expected value calculation unit (calculation unit) 35 access ratio information storage database (first D)
B) 37 Broadcast data and on-demand data storage database (second DB)

──────────────────────────────────────────────────続 き Continuation of the front page (51) Int.Cl. ⁷ Identification symbol FI Theme coat ゛ (Reference) H04N 7/173 610 H04L 13/00 303Z 5K034 9A001 (72) Inventor Satoshi Hakomori Toyosu 3-chome, Koto-ku, Tokyo No. 3 NTT Data Communications Co., Ltd. (72) Inventor Shio Inoue 3-3-3 Toyosu, Koto-ku, Tokyo NTT Data Communications Co., Ltd. F-term (reference) 5B085 BE07 BG07 5C064 BA01 BB05 BC16 BC20 BD02 BD08 5K028 DD01 DD02 SS24 5K030 KA02 LD07 5K033 CB13 DA01 DB12 5K034 BB07 DD02 9A001 JJ71 JZ27

Claims (12)

[Claims] In an environment in which a client and a server communicate with each other through an asymmetric network, the server responds to a broadcast-type communication for transmitting a plurality of predetermined pieces of broadcast information during one broadcast cycle and to a request from the client. And on-demand communication for transmitting the broadcast information, and while simulating the broadcast frequency of each of the broadcast information in one broadcast cycle, a total value of each broadcast frequency obtained each time the variable is performed; Means for calculating an expected value of the waiting time of the client corresponding thereto; and subtracting the total value of the respective broadcast frequencies when the expected value is minimized from the broadcast type communication period into one broadcast period. Means for assigning the remainder to the cycle of the on-demand communication, respectively. 2. The broadcast cycle determining method according to claim 1, wherein the calculating means and the allocating means are provided in a server. 3. The broadcast cycle determining method according to claim 1, wherein the broadcast information has a broadcast priority determined in advance in accordance with a magnitude of an access ratio from the client. Period determination method. 4. The broadcast cycle determining method according to claim 1, wherein said calculating means changes the broadcast frequency of the broadcast information having the first priority and changes the broadcast frequency of all the remaining broadcast information. A broadcast cycle determination method, wherein a total value of the respective broadcast frequencies when the expected value is minimized is determined as a cycle of the broadcast-type communication while a broadcast frequency is fixed at 1. 5. The broadcast cycle determining method according to claim 1, wherein the broadcast frequency of each of the broadcast information is set to a priority of the broadcast after determining the cycle of the broadcast-type communication. A broadcast cycle determination method, wherein the broadcast cycle of the broadcast-type communication is set as an upper limit and the broadcast information having the highest priority is determined so as to have the largest number and to decrease as the priority decreases. 6. The broadcast cycle determining method according to claim 1, wherein said calculating means determines that the broadcast information having a certain priority and one of the broadcast information having a certain priority are determined.
With respect to the next lower broadcast information, the expected value was obtained by variably adjusting the mutual broadcast frequency so that the increase of one broadcast frequency became the decrease of the other broadcast frequency, and the expected value was minimized. A broadcast frequency value of the upper broadcast information at the time is determined as a broadcast frequency of the broadcast information. 7. The broadcast cycle determining method according to claim 6, wherein when there is broadcast information lower than the two pieces of broadcast information,
A broadcast cycle determination method, wherein the broadcast frequency of the higher-order broadcast information is obtained with the broadcast frequency fixed at one. 8. The broadcast cycle determining method according to claim 1, wherein said calculating means varies the total number of information to be transmitted as broadcast information while varying the total number of information. The broadcast frequency and the expected value of the waiting time are calculated, and the number of information and the broadcast frequency when the expected value is the minimum are determined as the total number of broadcast information and the broadcast frequency of each broadcast information. Decision method. 9. The broadcast cycle determining method according to claim 1, wherein a plurality of clients are provided. 10. The broadcast cycle determining method according to claim 1, wherein the client is a mobile client. 11. An environment in which a client and a server communicate with each other through an asymmetric network, wherein the server responds to a broadcast-type communication for transmitting a plurality of predetermined pieces of broadcast information during one broadcast cycle and to a request from the client. And on-demand communication for transmitting the broadcast information, and while simulating the broadcast frequency of each of the broadcast information in one broadcast cycle, a total value of each broadcast frequency obtained each time the variable is performed; A first step of calculating an expected value of the waiting time of the client corresponding to the first step; and a sum of the respective broadcast frequencies when the expected value is minimized is defined as a cycle of the broadcast communication, and this cycle is defined as one broadcast. A second step of allocating the remainder obtained by subtracting the remainder from the cycle to the cycle of the on-demand communication, respectively. 12. In an environment in which a client and a server communicate with each other through an asymmetric network, the server responds to a broadcast-type communication for transmitting a plurality of predetermined pieces of broadcast information during one broadcast cycle and to a request from the client. And on-demand communication for transmitting the broadcast information, and while simulating the broadcast frequency of each of the broadcast information in one broadcast cycle, a total value of each broadcast frequency obtained each time the variable is performed; Means for calculating an expected value of the waiting time of the client corresponding thereto; and subtracting the total value of the respective broadcast frequencies when the expected value is minimized from the broadcast type communication period into one broadcast period. Means for allocating the rest to the cycle of the on-demand communication, respectively, the client and the server in the broadcast cycle determination method, And loaded with computer-readable program medium a computer program for causing a computer to operate as the respective means.