CN100438501C

CN100438501C - dynamic information transmission method and system

Info

Publication number: CN100438501C
Application number: CNB2005100526380A
Authority: CN
Inventors: 胡志麟
Original assignee: BenQ Corp
Current assignee: BenQ Corp
Priority date: 2005-03-07
Filing date: 2005-03-07
Publication date: 2008-11-26
Anticipated expiration: 2025-03-07
Also published as: CN1832445A

Abstract

A dynamic information transmission method includes the following steps: obtaining the data object with the earliest sequence in each data object sequence from an input queue as a candidate data object; using a gain measurement function to calculate the measurement value of each candidate data object; and placing one of the candidate data objects into an output queue according to the measurement value.

Description

Dynamic information transmission method and system

技术领域 technical field

此发明涉及一种数据传送技术，特别是涉及一种动态信息传送方法及系统。The invention relates to a data transmission technology, in particular to a dynamic information transmission method and system.

背景技术 Background technique

许多当今的数据密集的应用软件，如电子议价与投标、信息新闻分发、代理服务与网络搜寻等，牵涉到数个服务器以及为数众多的客户端。然而，特别是当上传与下载的信息流或频宽容量不对称时，传统以招揽式(pull-based)或主从式(client-server)的数据传送形态，通常会遭遇到可扩充性(scalability)以及效能降低的问题。相反地，推播式(push-based)数据广播模型则拥有较佳的客户端可扩充性。数据广播的核心概念为，服务器不需要接收到特定的请求，即可周期性地广播数据给那些监听广播频道(broadcast channel)并取得数据对象的客户端。Many of today's data-intensive applications, such as electronic bargaining and bidding, information news distribution, proxy services, and web search, involve several servers and numerous clients. However, especially when the upload and download information flow or bandwidth capacity is asymmetrical, the traditional pull-based or client-server data transmission form usually encounters scalability ( scalability) and reduced performance. On the contrary, the push-based data broadcasting model has better client scalability. The core concept of data broadcasting is that the server does not need to receive specific requests to periodically broadcast data to clients who listen to the broadcast channel and obtain data objects.

虽然很多应用软件采用数据广播的技术，但大多根植于传统数据管理的技术，亦即是一个数据对象通常仅对应到数据库中的一对状态与值。在这样的环境中，对照一个简单询问(query)/交易(transaction)，数据对象为独立、固定且不变。当成功地处理一个简单询问或读取交易时，客户端可在广播频道上取得相应的数据对象。然而，实务上，较新的应用软件所传送的数据对象为动态数据对象，且用以响应复杂询问以满足存取多个数据对象的请求。在动态的环境下，需要实时处理数据流(data stream)，而非先储存起来以响应较晚的询问。更甚者，动态数据对象间会具有关联，例如网页间的锚接关联(anchor relationship)或关联性数据库的参考完整性约束关联(referential integrity constraint for relationships)。使得数据对象间会有相关性或依赖关系，并且可被动态产生。所以，需要一种动态信息传送方法及系统，用以传送动态产生的数据对象。Although many application software adopt data broadcasting technology, most of them are rooted in traditional data management technology, that is, a data object usually only corresponds to a pair of state and value in the database. In such an environment, data objects are independent, fixed and immutable compared to a simple query/transaction. When successfully processing a simple query or read transaction, the client can get the corresponding data object on the broadcast channel. In practice, however, the data objects transmitted by newer applications are dynamic data objects and are used in response to complex queries to satisfy requests to access multiple data objects. In a dynamic environment, data streams need to be processed in real time, rather than stored in response to later queries. What's more, dynamic data objects may have associations, such as anchor relationships between web pages or referential integrity constraints for relationships in relational databases. So that there will be correlation or dependency between data objects, and can be dynamically generated. Therefore, there is a need for a dynamic information transmission method and system for transmitting dynamically generated data objects.

发明内容Contents of the invention

有鉴于此，本发明的目的为提供一种动态信息传送方法及系统，用以传送动态产生的数据对象。In view of this, the object of the present invention is to provide a dynamic information transmission method and system for transmitting dynamically generated data objects.

本发明实施例揭露的一种动态信息传送方法，使用一个处理单元执行，用以安排多个信息服务处理器的数据对象序列至一个输出队列。数据对象序列中包括多个具顺序性的数据对象。其方法包含下列步骤：由输入队列中取得相应于每一数据对象序列中的具最早顺位的数据对象当作候选数据对象；使用增益衡量函数计算每一候选数据对象的衡量值；以及依据衡量值将候选数据对象中的一者放置入输出队列，使得被放置入的候选数据对象可通过输出队列被广播至客户端装置，并且被放置入的数据对象可较其它数据对象更早被广播至客户端装置。A dynamic information transmission method disclosed in the embodiment of the present invention is executed by a processing unit to arrange the data object sequences of multiple information service processors to an output queue. The data object sequence includes multiple sequential data objects. The method comprises the following steps: obtaining the data object with the earliest sequence corresponding to each data object sequence from the input queue as a candidate data object; using a gain measurement function to calculate the measurement value of each candidate data object; and according to the measurement The value places one of the candidate data objects into the output queue, so that the placed candidate data object can be broadcast to the client device through the output queue, and the placed data object can be broadcast to the client device earlier than other data objects client device.

本发明实施例另揭露一种计算机可读取储存媒体，储存一个计算机程序，当此计算机程序被执行时，执行上述的动态信息传送方法。The embodiment of the present invention further discloses a computer-readable storage medium storing a computer program. When the computer program is executed, the above dynamic information transmission method is executed.

本发明实施例更揭露一种动态信息传送系统，用以安排多个信息服务处理器的数据对象序列至输出队列。每一数据对象序列中包括多个具顺序性的数据对象。动态信息传送系统包含输入队列以及处理单元。此处理单元耦接于输入队列，由上述输入队列中取得相应于每一数据对象序列中的具最早顺位的数据对象当作候选数据对象；使用增益衡量函数计算每一候选数据对象的一衡量值；以及依据衡量值将候选数据对象中的一者放置入输出队列，使得被放置入的候选数据对象可通过输出队列被广播至客户端装置，并且被放置入的数据对象可较其它数据对象更早被广播至客户端装置。The embodiment of the present invention further discloses a dynamic information delivery system for arranging the data object sequences of multiple information service processors to the output queue. Each data object sequence includes multiple sequential data objects. The dynamic messaging system includes input queues and processing units. The processing unit is coupled to the input queue, and obtains the data object with the earliest sequence corresponding to each data object sequence from the above input queue as a candidate data object; calculates a measure of each candidate data object using a gain measure function value; and placing one of the candidate data objects into the output queue according to the metric value, so that the placed candidate data object can be broadcast to the client device through the output queue, and the placed data object can be compared to other data objects broadcast to client devices earlier.

被放置入的候选数据对象可具有较其它候选数据对象为大的衡量值。增益衡量函数可用以将相应于相同信息服务处理器的具顺序性的数据对象安排得更紧密。被放置入的候选数据对象所关联的数据对象序列可拥有较少的数据对象。增益衡量函数可考量候选数据对象所关联的数据对象序列中的数据对象间的距离来计算衡量值。A candidate data object to be placed may have a larger metric value than other candidate data objects. The gain scaling function can be used to arrange sequential data objects corresponding to the same message service processor more closely. The sequence of data objects associated with the placed candidate data objects may have fewer data objects. The gain measure function may consider the distance between data objects in the sequence of data objects associated with the candidate data objects to calculate the measure value.

增益衡量函数可为The gain measure function can be

$G G (({d d}_{i i}^{k k})) = = - - {q q}_{k k} \cdot &Center Dot; {n no}_{k k},,$

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选数据对象中的一者，q_k代表第k个信息服务处理器被客户端装置订阅的程度的权重，n_k代表第k个信息服务处理器在一固定时间区间中产生数据对象的总数。Wherein, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is one of the candidate data objects, and q _k represents the weight of the degree to which the k-th information service processor is subscribed by the client device , _nk represents the total number of data objects generated by the kth information service processor in a fixed time interval.

增益衡量函数可为The gain measure function can be

$G G (({d d}_{i i}^{k k})) = = {q q}_{k k} \cdot &Center Dot; L L - - {q q}_{k k} \cdot &Center Dot; (({dd dd}_{i i + + 11,, i i + + 22}^{k k} + + . . . . . . + + {dd dd}_{nk nk,, 11}^{k k} + + . . . . . . + + {dd dd}_{i i - - 11 . . i i}^{k k})),,$

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选数据对象中的一者，q_k代表第k个信息服务处理器被客户端装置订阅的程度的权重，L代表一固定时间区间的时段总数，dd_i+1，i+2 ^k代表d_i+1 ^k与d_i+2 ^k间的有向距离，dd_nk，1 ^k代表d_nk ^k与d_l ^k间的有向距离，dd_i-1，i ^k代表d_i-1 ^k与d_i ^k间的有向距离。Wherein, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is one of the candidate data objects, and q _k represents the weight of the degree to which the k-th information service processor is subscribed by the client device , L represents the total number of periods in a fixed time interval, dd _{i+1, i+2} ^k represents the directed distance between d _i+1 ^k and d _i+2 ^k , dd _{nk, 1} ^k represents d _nk ^k and d _l The directed distance between ^k , dd _{i-1, i} ^k represents the directed distance between d _i-1 ^k and d _i ^k .

增益衡量函数可为The gain measure function can be

$G G (({d d}_{i i}^{k k})) = = {q q}_{k k} \cdot &Center Dot; \frac{{((\frac{L L}{{n no}_{k k}} - - {dd dd}_{i i - - 11,, i i}^{k k}))}^{22}}{{((\frac{L L}{{n no}_{k k}}))}^{22}},,$

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选数据对象中的一者，q_k代表第k个信息服务处理器被客户端装置订阅的程度的权重，L代表一固定时间区间的时段总数，n_k代表第k个信息服务处理器在固定时间区间中产生数据对象的总数，dd_i-1，i ^k代表d_i-1 ^k与d_i ^k间的有向距离。Wherein, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is one of the candidate data objects, and q _k represents the weight of the degree to which the k-th information service processor is subscribed by the client device , L represents the total number of periods in a fixed time interval, n _k represents the total number of data objects generated by the kth information service processor in a fixed time interval, dd _{i-1, i} ^k represents the interval between d _i-1 ^k and d _i ^k The directed distance of .

增益衡量函数可为The gain measure function can be

$G G (({d d}_{i i}^{k k})) = = {q q}_{k k} \cdot &Center Dot; \frac{{((\frac{L L}{{n no}_{k k}} - - {dd dd}_{i i - - 11,, i i}^{k k}))}^{22}}{{((\frac{L L}{{n no}_{k k}}))}^{22}} \cdot \cdot \underset{11 \leq \leq i i \leq \leq {n no}_{k k} - - 11}{Σ Σ} (({dd dd}_{i i,, i i + + 11}^{k k} - - ((22 \frac{L L}{{n no}_{k k}} - - {dd dd}_{i i - - 11,, i i}^{k k})))),,$

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选数据对象中的一者，q_k代表第k个信息服务处理器被客户端装置订阅的程度的权重，L代表固定时间区间的时段总数，n_k代表第k个信息服务处理器在固定时间区间中产生数据对象的总数，dd_i-1，i ^k代表d_i-1 ^k与d_i ^k间的有向距离，dd_i，i+1 ^k代表d_i ^k与d_i+1 ^k间的有向距离。Wherein, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is one of the candidate data objects, and q _k represents the weight of the degree to which the k-th information service processor is subscribed by the client device , L represents the total number of periods in a fixed time interval, n _k represents the total number of data objects generated by the kth information service processor in a fixed time interval, dd _{i-1, i} ^k represents the time interval between d _i-1 ^k and d _i ^k Directed distance, dd _{i, i+1} ^k represents the directed distance between d _i ^k and d _i+1 ^k .

附图说明 Description of drawings

图1是表示依据本发明实施例的动态信息传送系统的网络架构图；Fig. 1 is a network architecture diagram representing a dynamic information transmission system according to an embodiment of the present invention;

图2是表示依据本发明实施例的应用于动态信息传送系统中的广播服务器或客户端装置的硬件架构方块图；FIG. 2 is a block diagram showing a hardware architecture of a broadcast server or a client device applied in a dynamic information transmission system according to an embodiment of the present invention;

图3是表示依据本发明实施例的数据传送示意图；FIG. 3 is a schematic diagram showing data transmission according to an embodiment of the present invention;

图4是表示依据本发明实施例的数据广播排程示意图；FIG. 4 is a schematic diagram showing a data broadcast schedule according to an embodiment of the present invention;

图5是表示依据本发明实施例的动态信息传送方法的方法流程图；FIG. 5 is a flow chart showing a method for transmitting dynamic information according to an embodiment of the present invention;

图6是表示依据本发明实施例的储存媒体示意图。FIG. 6 is a schematic diagram showing a storage medium according to an embodiment of the present invention.

附图符号说明Description of reference symbols

11-处理单元；12-内存；13-储存装置；14-输出装置；15-输入装置；16-通信装置；17-总线；20-网络架构；21-广播服务器；22、23、24-客户端装置；30-网络；31-输出队列；32-输入队列；33a、33b、...、33m-信息服务处理器；34-广播频道；S511、S513、S515、S517、S521-流程步骤；60-储存媒体；620-动态信息传送计算机程序；621-判断输入队列是否为空队列逻辑；622-由输入队列中取得相应于每一信息服务处理器的最早数据对象逻辑并储存至候选集合逻辑；623-使用增益衡量函数决定候选集合中的一数据对象逻辑；624-将决定的数据对象送到输出队列逻辑；625-等待一个时段逻辑。11-processing unit; 12-memory; 13-storage device; 14-output device; 15-input device; 16-communication device; 17-bus; 20-network architecture; 21-broadcast server; 22, 23, 24-client Terminal device; 30-network; 31-output queue; 32-input queue; 33a, 33b, ..., 33m-information service processor; 34-broadcast channel; S511, S513, S515, S517, S521-process steps; 60-storage medium; 620-dynamic information transmission computer program; 621-judging whether the input queue is an empty queue logic; 622-obtaining the earliest data object logic corresponding to each information service processor from the input queue and storing it in the candidate set logic ; 623-using the gain measure function to determine a data object logic in the candidate set; 624-sending the determined data object to the output queue logic; 625-waiting for a period logic.

具体实施方式 Detailed ways

图1是表示依据本发明实施例的动态信息传送系统的网络架构图。在较佳的情况下，此网络架构20包括广播服务器21、客户端装置22、23与24。其中，客户端装置22、23与24可以实体联机(wired-connection)、无线或混合实体联机与无线的方式，通过各式各样的网络30，连接至广播服务器21。而熟习此技艺者皆了解客户端装置22、23与24与广播服务器(broadcastingserver)21间的连结也许须通过多个中介节点，例如，无线接入点(accesspoint)、基站(base station)、集线器(hub)、桥接器(bridge)、路由器(router)或其它用以处理网络通信的中介节点。FIG. 1 is a network architecture diagram showing a dynamic information transmission system according to an embodiment of the present invention. In a preferred situation, the network architecture 20 includes a broadcast server 21 , client devices 22 , 23 and 24 . Wherein, the client devices 22 , 23 and 24 can be connected to the broadcast server 21 through various networks 30 through wired-connection, wireless or a combination of wired-connection and wireless. Those skilled in the art will understand that the connection between the client devices 22, 23 and 24 and the broadcasting server (broadcasting server) 21 may have to pass through multiple intermediary nodes, such as wireless access points (accesspoints), base stations (base stations), hubs (hub), bridge (bridge), router (router) or other intermediary nodes used to handle network communication.

图2是表示依据本发明实施例的应用于动态信息传送系统中的广播服务器21、客户端装置22、23或24的硬件架构方块图。广播服务器21以及个人计算机22与23中的一者，包括处理单元11、内存12、储存装置13、输出装置14、输入装置15、通信装置16，并使用总线17将其连结在一起。除此之外，熟习此技艺人士也可将广播服务器21、客户端装置22、23与24中的任一者实施于其它计算机系统样态(configuration)上，例如，手持式设备(hand-held devices)、多处理器系统、以微处理器为基础或可程序化的消费性电子产品(microprocessor-based or programmable consumerelectronics)、网络计算机、迷你计算机、大型主机以及类似的设备。处理单元11可包含一单一中央处理单元(central-processing unit；CPU)或者是关联于平行运算环境(parallel processing environment)的多个平行处理单元。内存12包含只读存储器(read only memory；ROM)、闪存(flash ROM)以及/或动态存取存储器(random access memory；RAM)，用以储存可供处理单元11执行的程序模块。一般而言，程序模块包含常序(routines)、程序(program)、对象(object)、组件(component)等，用以执行动态信息传送或接收功能。本发明亦可以实施于分布式运算环境，其运算工作被一连结于网络30的远程处理设备所执行。在分布式环境中，广播服务器21的功能执行，也许由本地以及多部远程计算机系统共同完成。储存装置13包含硬盘装置、软盘装置、光盘装置或随身听装置，用以读取硬盘、软盘、光盘、随身碟中储存的程序模块以及/或数据对象。通信装置16可为有线网络卡或符合GPRS、802.11规格的无线网络卡。FIG. 2 is a block diagram showing the hardware architecture of the broadcast server 21 , the client device 22 , 23 or 24 applied in the dynamic information transmission system according to the embodiment of the present invention. The broadcast server 21 and one of the personal computers 22 and 23 include a processing unit 11 , a memory 12 , a storage device 13 , an output device 14 , an input device 15 , and a communication device 16 , which are connected together by a bus 17 . In addition, those skilled in the art can also implement any one of the broadcast server 21, the client devices 22, 23, and 24 on other computer system configurations, such as hand-held devices. devices), multiprocessor systems, microprocessor-based or programmable consumer electronics, network computers, minicomputers, mainframes, and similar devices. The processing unit 11 may include a single central-processing unit (CPU) or a plurality of parallel processing units associated with a parallel processing environment (parallel processing environment). The memory 12 includes a read only memory (ROM), a flash memory (flash ROM) and/or a dynamic access memory (random access memory; RAM) for storing program modules that can be executed by the processing unit 11. Generally speaking, program modules include routines, programs, objects, components, etc., and are used to perform dynamic information transmission or reception functions. The invention may also be practiced in distributed computing environments where computing tasks are performed by remote processing devices linked through network 30 . In a distributed environment, the functions of the broadcast server 21 may be performed by local and multiple remote computer systems. The storage device 13 includes a hard disk device, a floppy disk device, an optical disk device, or a walkman device, and is used for reading program modules and/or data objects stored in the hard disk, floppy disk, optical disk, or flash drive. The communication device 16 can be a wired network card or a wireless network card conforming to GPRS and 802.11 specifications.

图3是表示依据本发明实施例的数据传送示意图。信息服务处理器33a、33b至33m动态产生数据对象，通过广播服务器21有效率地传送，接着，循序地传送到客户端装置。当数据对象被有计划地安排到广播频道(broadcastchannel)34时，由同一信息服务处理器所产生的多个数据对象，可被视为具顺序性关联的数据对象。数据对象可包括音乐、影片、图形、文件、网页、数据库纪录或其它形态的数据。服务存取时间是指由一个客户端装置请求一个信息服务处理器的时点，一直到此信息服务处理器的所有数据对象被完整下载的一段时间区间。广播服务器21以周期性为基础来进行实时广播安排，藉由缩短服务存取平均时间(mean service access time)来做最佳化的广播排程(broadcasting schedule)31的安排。FIG. 3 is a schematic diagram showing data transmission according to an embodiment of the present invention. The information service processors 33a, 33b to 33m dynamically generate data objects, efficiently transmit them through the broadcast server 21, and then sequentially transmit them to the client devices. When the data objects are scheduled to broadcast channel (broadcast channel) 34, multiple data objects generated by the same message service processor can be regarded as sequentially associated data objects. Data objects may include music, video, graphics, documents, web pages, database records, or other forms of data. The service access time refers to a period of time from the time point when a client device requests an information service processor until all data objects of the information service processor are completely downloaded. The broadcast server 21 performs real-time broadcast scheduling on a periodic basis, and optimizes the broadcasting schedule 31 by shortening the mean service access time.

图4是表示依据本发明实施例的数据广播排程示意图。假定S代表m个信息服务处理器S₁、S₂至S_m的集合。每一个信息服务处理器拥有一个对象产生率(object production rate)O_k，代表此信息服务处理器在一个固定时间区间I中产生n_k个固定长度对象。所以，广播服务器21在每个固定时间区间I中拥有N＝n₁+n₂+...+n_m＝∑_1≤k≤mn_k个物件。假设采用一个时段化模型(slottedmodel)，每次使用一个时段(slot)来广播一个物件。一个广播周期(broadcastcycle，以L来表示)，等于一个周期性广播排程(periodic broadcastschedule，以P_i来表示)所递送的时段总数。在时间轴(time horizon)上的无穷排程(infinite schedule，以P来表示)为∪_i＝1 ^∞P_i，其中P_i为在第i个时间区间由m个信息服务处理器所产生的N个动态顺序性对象。详而言之，P为一d₁，…，d_i，…，d_j，…，d_N的序列，其中d_i≠d_j，并且1≤i，j≤N。所以，L＝I＝P。为简化说明，若d_i∈S_k，则在P中的对象d_i表示为d_i ^k，此定义在N个连续时段的区间的信息服务处理器S_k所产生的对象顺序为 $O_{k} = < d_{1}^{k}, d_{2}^{k}, \cdot \cdot \cdot, d_{n_{k}}^{k} > .$ 服务存取时间，以T_k(t)表示，是指在P中，由一个客户端装置请求S_k的时点，一直到S_k的n_k个连续数据对象被完整下载的一段时间区间。给定S_k所产生的任意两个对象d_i ^k与d_j ^k，且0≤i≤j≤n_k，P(d_i ^k)与户(d_j ^k)分别表示在一周期时间L中的P的d_i ^k与d_j ^k的时段位置。d_i ^k与d_j ^k之间为有向距离(directed distance)，表示为 ${dd}_{i, j}^{k} = (P (d_{i}^{k}) - P (d_{j}^{k})) \mod L .$ FIG. 4 is a schematic diagram showing a data broadcast schedule according to an embodiment of the present invention. It is assumed that S represents a set of m information service processors S ₁ , S ₂ to S _m . Each information service processor has an object production rate (object production rate) O _k , which means that the information service processor produces _nk fixed-length objects in a fixed time interval I. Therefore, the broadcast server 21 has N=n ₁ +n ₂ +...+n _m =Σ _1≤k≤m n _k objects in each fixed time interval I. Assuming a slotted model is adopted, one slot is used to broadcast one object at a time. A broadcast cycle (represented by L) is equal to the total number of time slots delivered by a periodic broadcast schedule (represented by _Pi ). The infinite schedule (indicated by P) on the time axis (time horizon) is ∪ _i=1 ^∞ P _i , where P _i is generated by m information service processors in the i-th time interval N dynamic sequential objects. In detail, P is a sequence of d ₁ ,...,d _i ,...,d _j ,...,d _N , where d _i ≠d _j , and 1≤i, j≤N. Therefore, L=I=P. To simplify the description, if d _i ∈ S _k , then the object d _i in P is expressed as d _i ^k , which defines the sequence of objects generated by the information service processor S _k in the interval of N consecutive periods as $o_{k} = < d_{1}^{k}, d_{2}^{k}, \cdot \cdot \cdot, d_{{no}_{k}}^{k} > .$ Service access time, denoted by T _k (t), refers to a period of time in P from the time point when a client device requests S _k until the n _k consecutive data objects of S _k are completely downloaded. Given any two objects d _i ^k and d _j ^k generated by S _k , and 0≤i≤j≤n _k , P(d _i ^k ) and household (d _j ^k ) are represented in a cycle time L The period positions of d _i ^k and d _j ^k of P. The directed distance between d _i ^k and d _j ^k is expressed as ${dd}_{i, j}^{k} = (P (d_{i}^{k}) - P (d_{j}^{k})) \mod L .$

为符合动态信息传送环境，动态信息传送方法的最主要原则为在一无限与周期性排程中，将相同信息服务处理器所产生的顺序性数据对象尽可能地安排的紧密一点。用以让广播服务器21决定输出队列31中的下一个广播数据对象。图5是表示依据本发明实施例的动态信息传送方法的方法流程图。此方法可由广播服务器21中的处理单元11执行，开始于步骤S511，判断输入队列32是否为空队列，是则执行步骤S521，否则执行步骤S513。在步骤S521，等待一个时段。在步骤S513，由输入队列32中分别取得相应于每一信息服务处理器S₁、S₂至S_m的具最早顺位的数据对象，并将其储存至一候选集合中。步骤S515，使用增益衡量函数(Gain Measure Function，GMF)计算候选集合中的每一个数据对象的增益衡量值，并将拥有最大增益衡量值的数据对象放置到输出队列31中，使得当此数据对象被放置到输出队列31时，拥有较佳的广播效率(亦可为拥有较小的服务存取平均时间)。在步骤S517，将决定的数据对象放置到输出队列31。广播处理单元(未显示)会依据先进先出(First-In-First-Out，FIFO)的原则，将输出队列31的数据对象传送给适当的客户端装置。In order to comply with the dynamic information transmission environment, the main principle of the dynamic information transmission method is to arrange the sequential data objects generated by the same information service processor as closely as possible in an infinite and periodic schedule. It is used for the broadcast server 21 to determine the next broadcast data object in the output queue 31 . FIG. 5 is a flow chart showing a method for transmitting dynamic information according to an embodiment of the present invention. This method can be executed by the processing unit 11 in the broadcast server 21 , and starts from step S511 , judging whether the input queue 32 is an empty queue, if yes, execute step S521 , otherwise execute step S513 . In step S521, wait for a period of time. In step S513, the data object with the earliest order corresponding to each information service processor S ₁ , S ₂ to S _m is obtained from the input queue 32 and stored in a candidate set. Step S515, using the gain measure function (Gain Measure Function, GMF) to calculate the gain measure value of each data object in the candidate set, and placing the data object with the maximum gain measure value in the output queue 31, so that when the data object When placed in the output queue 31, it has better broadcast efficiency (or has a smaller average service access time). In step S517 , the determined data object is placed in the output queue 31 . The broadcast processing unit (not shown) transmits the data objects in the output queue 31 to appropriate client devices according to the first-in-first-out (FIFO) principle.

增益衡量函数可为如以下所示的公式(1)、(2)、(3)与(4)中的一者：The gain scaling function may be one of formulas (1), (2), (3) and (4) as shown below:

$G_{1} (d_{i}^{k}) = - q_{k} \cdot n_{k}$ .............................................公式(1) $G_{1} (d_{i}^{k}) = - q_{k} \cdot {no}_{k}$ .............................................Formula 1)

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选集合中的数据对象，q_k为一个权重，代表第k个信息服务处理器被客户端装置订阅的程度，n_k代表第k个信息服务处理器在一个固定时间区间L中产生固定长度对象的总数。为了降低服务存取平均时间，公式(1)将关联于产生较多固定长度对象的信息服务处理器的对象尽可能地延迟并放置到输出队列31的后面。Among them, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is a data object in the candidate set, q _k is a weight, representing the k-th information service processor subscribed by the client device degree, _nk represents the total number of fixed-length objects generated by the kth information service processor in a fixed time interval L. In order to reduce the average service access time, the formula (1) delays the objects associated with the message service processor that generates more fixed-length objects as much as possible and places them at the back of the output queue 31 .

$G_{2} (d_{i}^{k}) = q_{k} \cdot L - q_{k} \cdot ({dd}_{i + 1, i + 2}^{k} + . . . + {dd}_{n_{k}, 1}^{k} + . . . + {dd}_{i + 1, i}^{k})$ .....公式(2) $G_{2} (d_{i}^{k}) = q_{k} &Center Dot; L - q_{k} &Center Dot; ({dd}_{i + 1, i + 2}^{k} + . . . + {dd}_{{no}_{k}, 1}^{k} + . . . + {dd}_{i + 1, i}^{k})$ .....Formula (2)

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选集合中的数据对象，q_k为一个权重，代表第k个信息服务处理器被客户端装置订阅的程度，L代表周期性广播排程所递送的时段总数，dd_i+1，i+2 ^k代表d_i+1 ^k与d_i+2 ^k间的有向距离，dd_nk，1 ^k代表d_nk ^k与d₁ ^k间的有向距离，而dd_i-1，i ^k代表d_i-1 ^k与d_i ^k间的有向距离。在有限的周期性广播排程L的情况下，更多的剩余空间代表接续的n_k-1个对象＜d_i+2 ^k，…，d_nk ^k，d₁ ^k，…，d_i ^k＞排列得越紧密。Among them, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is a data object in the candidate set, q _k is a weight, representing the k-th information service processor subscribed by the client device degree, L represents the total number of time slots delivered by the periodic broadcast schedule, dd _{i+1, i+2} ^k represents the directed distance between d _i+1 ^k and d _i+2 ^k , dd _{nk, 1} ^k represents d _nk The directed distance between ^k and d ₁ ^k , and d _{i-1, i} ^k represents the directed distance between d _i-1 ^k and d _i ^k . In the case of a finite periodic broadcast schedule L, more remaining space represents _nk −1 objects in succession <d _i+2 ^k ,...,d _nk ^k ,d ₁ ^k ,...,d _i ^k > The tighter the arrangement.

$G_{3} (d_{i}^{k}) = q_{k} \cdot \frac{{(\frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})}^{2}}{{(\frac{L}{n_{k}})}^{2}}$ ....................................公式(3) $G_{3} (d_{i}^{k}) = q_{k} \cdot \frac{{(\frac{L}{{no}_{k}} - {dd}_{i - 1, i}^{k})}^{2}}{{(\frac{L}{{no}_{k}})}^{2}}$ .................................Formula (3)

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选集合中的数据对象，q_k为一个权重，代表第k个信息服务处理器被客户端装置订阅的程度，L代表周期性广播排程所递送的时段总数，n_k代表第k个信息服务处理器在一个固定时间区间L中产生固定长度对象的总数，而dd_i-1，j ^k代表d_i-1 ^k与d_i ^k间的有向距离。在公式(3)中，只考虑每一个信息服务处理器中的单一个数据对象，而不考虑先前广播的数据对象。Among them, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is a data object in the candidate set, q _k is a weight, representing the k-th information service processor subscribed by the client device degree, L represents the total number of periods delivered by the periodic broadcast schedule, n _k represents the total number of fixed-length objects generated by the kth information service processor in a fixed time interval L, and dd _{i-1, j} ^k represents d _{i -1} Directed distance between ^k and d _i ^k . In formula (3), only a single data object in each message service processor is considered, regardless of previously broadcast data objects.

$G_{4} (d_{i}^{k}) = G_{3} (d_{i}^{k}) \cdot \underset{1 \leq i \leq n_{k} - 1}{Σ} ({dd}_{i, i + 1}^{k} - (2 \frac{L}{n_{k}} - {dd}_{i - 1, i}^{k}))$ ...............公式(4) $G_{4} (d_{i}^{k}) = G_{3} (d_{i}^{k}) &Center Dot; \underset{1 \leq i \leq {no}_{k} - 1}{Σ} ({dd}_{i, i + 1}^{k} - (2 \frac{L}{{no}_{k}} - {dd}_{i - 1, i}^{k}))$ ................Formula (4)

其中，d_i ^k代表相应于第k个信息服务处理器的第i个数据对象且为候选集合中的数据对象，L代表周期性广播排程所递送的时段总数，n_k代表第k个信息服务处理器在一个固定时间区间L中产生固定长度对象的总数，dd_i，i+1 ^k代表d_i ^k与d_i+1 ^k间的有向距离，而dd_i-1，i ^k代表d_i-1 ^k与d_i ^k间的有向距离。相较于公式(3)，公式(4)更考虑对象序列O_k中先前的n_k-1个数据对象分别与下一个对象d_i+1 ^k的间所可能带来的增益。Among them, d _i ^k represents the i-th data object corresponding to the k-th information service processor and is a data object in the candidate set, L represents the total number of time periods delivered by the periodic broadcast schedule, n _k represents the k-th information The service processor generates the total number of fixed-length objects in a fixed time interval L, dd _{i, i+1} ^k represents the directed distance between d _i ^k and d _i+1 ^k , and dd _{i-1, i} ^k represents d The directed distance between _i-1 ^k and d _i ^k . Compared with the formula (3), the formula (4) considers the possible gain between the previous _nk −1 data objects in the object sequence _Ok and the next object d _i+1 ^k respectively.

再者，本发明提出一种储存媒体，用以储存一计算机程序，上述计算机程序用以实现动态信息传送方法，此方法会执行如上所述的步骤。图6是表示依据本发明实施例的储存媒体示意图。此储存媒体60，用以储存动态信息传送计算机程序620。其计算机程序包含五个逻辑，分别为判断输入队列是否为空队列逻辑621、由输入队列中取得相应于每一信息服务处理器的具最早顺位的数据对象并储存至候选集合逻辑622、使用增益衡量函数决定候选集合中的一数据对象逻辑623、将决定的数据对象送到输出队列逻辑624、等待一个时段逻辑625。Furthermore, the present invention proposes a storage medium for storing a computer program, and the above computer program is used to implement a method for transmitting dynamic information, and the method will execute the above-mentioned steps. FIG. 6 is a schematic diagram showing a storage medium according to an embodiment of the present invention. The storage medium 60 is used for storing the dynamic information transmission computer program 620 . Its computer program includes five logics, which are judging whether the input queue is an empty queue logic 621, obtaining the data object with the earliest sequence corresponding to each information service processor from the input queue and storing it in the candidate set logic 622, using The gain weight function determines a data object logic 623 in the candidate set, sends the determined data object to the output queue logic 624 , and waits for a period of time logic 625 .

虽然本发明已以较佳实施例揭露如上，然其并非用以限定本发明，任何熟悉此项技艺者，在不脱离本发明的精神和范围内，当可做些许更动与润饰，因此本发明的保护范围当视后附的申请专利范围所界定者为准。Although the present invention has been disclosed above with preferred embodiments, it is not intended to limit the present invention. Anyone familiar with this art can make some changes and modifications without departing from the spirit and scope of the present invention. Therefore, this The scope of protection of the invention shall be defined by the scope of the appended patent application.

Claims

1. a dynamic information transmission method uses a processing unit to carry out, and in order to arrange data object sequence to an output queue of a plurality of information service processors, comprises the data object of a plurality of tool successions in each above-mentioned data object sequence, and its method comprises:

By obtain in the input rank corresponding to the tool in each above-mentioned data object sequence the earliest a data object of cis-position be used as a candidate data object;

Use a gain to weigh a metric of each above-mentioned candidate data object of function calculation; And

According to above-mentioned metric one in the above-mentioned candidate data object is placed into above-mentioned output queue, make the above-mentioned candidate data object that is placed into to be broadcast to a client terminal device by above-mentioned output queue, and the above-mentioned data object that is placed into can more early be broadcast to above-mentioned client terminal device than other data object.

2. dynamic information transmission method as claimed in claim 1, wherein, it is big above-mentioned metric that the above-mentioned candidate data object that is placed into has than other candidate data object.

3. dynamic information transmission method as claimed in claim 1, wherein, above-mentioned gain is weighed function in order to arranging closelyr than the data object of other tool succession corresponding to the data object of the tool succession of identical information service processor.

4. dynamic information transmission method as claimed in claim 1, wherein, the associated above-mentioned data object sequence of the above-mentioned candidate data object that is placed into has less data object than other data object sequence.

5. dynamic information transmission method as claimed in claim 4, wherein, above-mentioned gain is weighed function and is

G (d_{i}^{k}) = - q_{k} \cdot n_{k},

Wherein, d _i ^kRepresentative is corresponding to i data object of k information service processor and be one in the above-mentioned candidate data object, q _kRepresent the weight of the degree that k information service processor subscribed to by above-mentioned client terminal device, n _kRepresent k information service processor in a set time interval, to produce the sum of data object.

6. dynamic information transmission method as claimed in claim 1, wherein, above-mentioned gain is weighed function and is considered that the distance between data object in the associated above-mentioned data object sequence of above-mentioned candidate data object calculates above-mentioned metric.

7. dynamic information transmission method as claimed in claim 6, wherein, above-mentioned gain is weighed function and is

G (d_{i}^{k}) = q_{k} \cdot \frac{{(\frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})}^{2}}{{(\frac{L}{n_{k}})}^{2}},

Wherein, d _i ^kRepresentative is corresponding to i data object of k information service processor and be one in the above-mentioned candidate data object, q _kRepresent the weight of the degree that k information service processor subscribed to by client terminal device, L represents the period sum in a set time interval, n _kRepresent k information service processor in the said fixing time interval, to produce the sum of data object, dd _{I-1, i} ^kRepresent d _I-1 ^kWith d _i ^kBetween directed distance.

8. dynamic information transmission method as claimed in claim 6, wherein, above-mentioned gain is weighed function and is

G (d_{i}^{k}) = q_{k} \cdot \frac{{(\frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})}^{2}}{{(\frac{L}{n_{k}})}^{2}} \cdot \underset{1 \leq i \leq n_{k} - 1}{Σ} ({dd}_{i, i + 1}^{k} - (2 \frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})),

Wherein, d _i ^kRepresentative is corresponding to i data object of k information service processor and be one in the above-mentioned candidate data object, q _kRepresent the weight of the degree that k information service processor subscribed to by client terminal device, L represents the period sum in a set time interval, n _kRepresent k information service processor in the said fixing time interval, to produce the sum of data object, dd _{I-1, i} ^kRepresent d _I-1 ^kWith d _i ^kBetween directed distance, dd _{I, i+1} ^kRepresent d _i ^kWith d _I+1 ^kBetween directed distance.

9. a multidate information transfer system in order to arrange data object sequence to an output queue of a plurality of information service processors, comprises the data object of a plurality of tool successions in each above-mentioned data object sequence, comprising:

One input rank; And

One processing unit, be coupled to above-mentioned input rank, by obtain in the above-mentioned input rank corresponding to the tool in each above-mentioned data object sequence the earliest a data object of cis-position be used as a candidate data object, use a gain to weigh a metric of each above-mentioned candidate data object of function calculation, and the above-mentioned metric of foundation is placed into above-mentioned output queue with one in the above-mentioned candidate data object

Make the above-mentioned candidate data object that is placed into to be broadcast to a client terminal device by above-mentioned output queue, and the above-mentioned data object that is placed into can more early be broadcast to above-mentioned client terminal device than other data object.

10. multidate information transfer system as claimed in claim 9, wherein, it is big above-mentioned metric that the above-mentioned candidate data object that is placed into has than other candidate data object.

11. multidate information transfer system as claimed in claim 9, wherein, above-mentioned gain is weighed function in order to arranging closelyr than the data object of other tool succession corresponding to the data object of the tool succession of identical information service processor.

12. multidate information transfer system as claimed in claim 9, wherein, the associated above-mentioned data object sequence of the above-mentioned candidate data object that is placed into has less data object than other data object sequence.

13. multidate information transfer system as claimed in claim 12, wherein, above-mentioned gain is weighed function and is

G (d_{i}^{k}) = - q_{k} \cdot n_{k},

14. multidate information transfer system as claimed in claim 9, wherein, above-mentioned gain is weighed function and is considered that the distance between data object in the associated above-mentioned data object sequence of above-mentioned candidate data object calculates above-mentioned metric.

15. multidate information transfer system as claimed in claim 14, wherein, above-mentioned gain is weighed function and is

G (d_{i}^{k}) = q_{k} \cdot \frac{{(\frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})}^{2}}{{(\frac{L}{n_{k}})}^{2}},

16. multidate information transfer system as claimed in claim 14, wherein, above-mentioned gain is weighed function and is

G (d_{i}^{k}) = q_{k} \cdot \frac{{(\frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})}^{2}}{{(\frac{L}{n_{k}})}^{2}} \cdot \underset{1 \leq i \leq n_{k} - 1}{Σ} ({dd}_{i, i + 1}^{k} - (2 \frac{L}{n_{k}} - {dd}_{i - 1, i}^{k})),

Wherein, d _i ^kRepresentative corresponding to i data object of k information service processor and be above-mentioned candidate data object one, q _kRepresent the weight of the degree that k information service processor subscribed to by client terminal device, L represents the period sum in a set time interval, n _kRepresent k information service processor in the said fixing time interval, to produce the sum of data object, dd _{I-1, i} ^kRepresent d _I-1 ^kWith d _i ^kBetween directed distance, dd _{I, i+1} ^kRepresent d _i ^kWith d _I+1 ^kBetween directed distance.