用于优化无线网络中多媒体流的前向纠错的方法和系统

摘要

通过响应于所计算的分组损失概率来调整一组纠错(EC)参数，可以以优选的方式使得通信系统中的分组损失最小化。从应用于一组通信参数的、所得出的算法中得到计算的概率。根据通信系统的柏努利分布业务模型和固定比特率(CBR)业务模型得出算法。收缩－状态模型被用于得出一种用于计算分组损失的近似概率的有效算法。还公开了算法的可选应用。

说明书

技术领域

本发明涉及优化用于处理布置在传输给接收机的分组中的信息流的装置的操作，更具体地来说，涉及调整该装置的操作以便在接收机使分组损失最小化。本发明可以被有利地用于在无线网络中传输携带多媒体信息的分组流的系统。

背景技术

在无线网络中实时多媒体业务的递送被期望是第三代蜂窝、WIFI和WIMAX无线网络中的重要应用。在这些应用中，诸如表示图象和声音的数字数据的多媒体信息被组织为分组。多媒体源将这些分组的流发送给如无线接入点的处理装置，这些处理装置将分组通过无线通信信道发送到终端用户接收机。如果处理装置不能立即发送分组，则把分组临时保存在队列或缓存中，直到它能被发送。例如，当无线通信信道正被其他处理装置使用时，处理装置不能发送分组。

许多因素能对终端用户接收的多媒体信息的感知质量产生不利的影响，所述因素包括分组损失(packet loss)、分组延迟和延迟抖动。分组损失包括没有被终端用户接收机接收的丢失分组和被接收但其携带的信息被损坏的损坏分组(corrupted packet)。引起分组损失的原因有：(1)噪声通信信道，(2)同时传输或在多个发送机发送分组的情况下的“冲突(collision)”，和(3)在处理装置中使用的在分组能被发送前暂时保存分组的缓存发生溢出。当处理装置必须临时在它的缓存中保存分组而该缓存已满时，会发生缓存溢出。由噪声通信信道和冲突引起的分组损失在此被称为I类损失，而由缓存溢出引起的分组损失在此被成为II类损失。

许多技术被提议用于减少I类和II类分组损失的感知影响。被称为前向纠错(Forward Error Correction，FEC)的技术使接收机能在引起损失的情形不太频繁且持续时间不长的情况下恢复由丢失或损坏的分组携带的信息。可由FEC处理的错误引起情况(error-causing condition)的持续时间和频率由两个参数n和k控制，其中(n-k)个“FEC分组”和k个多媒体分组被合并在一起以形成具有总数为n的多媒体+FEC分组的一组分组。如果接收机能无损坏地接收到这n个分组中的至少k个，则由丢失和损坏分组引起的任何损失都能被纠正。如果无损失地接收到的分组少于这n个分组中的k个，则一个或多个分组的信息损失不能被恢复。

不幸地是，FEC是有代价的。附加的(n-k)个FEC分组增加了由于冲突引起的延迟风险，并且增加了发送每组分组需要的时间或信道带宽。可以选择FEC参数(n，k)的值来优化竞争需求之间的平衡。较高的比率会增加可能的纠错等级，但也会增加延迟和增加因子所需要的信道带宽。

可以选择FEC参数(n，k)以满足对于指定分组损失率的保护、延迟和带宽需求。不幸地是，不可能同时满足所有的需求，可能需要各种需求间的折衷。此外，可获取的信道带宽对比率施加了实际的限制。非常高的比率对带宽需求产生影响，其引起来自其他数据源的分组缺乏或超出通信信道的可用带宽。FEC参数的最佳选择应考虑信道的可用带宽和由其他数据源提供的分组所需的带宽。

然而，实际上，通信系统中的情况变化得很快。以最小的带宽增加提供想要的保护等级的FEC参数最佳选择要求FEC参数值(n，k)被自适应地设置。所需要的是一种能通过具有低计算复杂度的处理实现的、用于调整这些FEC参数的方式。这使得FEC系统通过使用带有适度处理能力的装置就能实时调整其自身，所述装置能以低成本被结合到典型的网络设备中。

如果有周期测量情况并将那些测量提供给系统中用于调整FEC参数的部分的设备，则根据本发明的自适应FEC系统就能更有效地得以实现。在本公开文本的整个剩余部分中假设这样的测量设备是存在的。理论上，任何特定的测量设备对于本发明都不是必需的。简单地解释，以下讨论假设有一个设备可用于测量所需的所有传输速率和损失以作为对于以下描述的通信系统模型的输入参数。本发明的实施能使用这些测量以及其他参数来调整FEC参数值(n，k)，以使II类分组损失的影响最小化。

发明内容

本发明的目的在于使用计算有效的处理在分组通信系统中提供纠错参数的调整以使分组损失的影响最小化。

本发明的一个方面是在通信系统中控制分组的供应，所述通信系统包括：第一数据源，其提供携带布置在一组分组中的信息的源信号，该组分组包括第一数目的数据分组和第二数目的纠错分组；分组处理装置，接收源信号，将该组分组中的至少一些分组的信息保存在有缓存大小的缓存中，以及发送包括如下信息的分组的输出信号，即，所述信息中的至少一些被保存在缓存中，其中在该组分组中的至少一些分组的信息由于缓存已满引起的损失而从输出信号中被遗漏；和接收器，接收在输出信号中的至少一些分组，对这些接收的分组应用纠错处理以恢复被损坏或丢失的信息。该控制得以实现是通过(a)接收一个或多个携带参数的信号，这些参数表示缓存大小、第一数目和第二数目、在时间间隔内由分组处理装置接收来自第一数据源的分组的到达概率(arrival probability)、当缓存非空时分组处理装置在时间间隔内成功发送的分组的发送概率(transmission probability)以及在时间间隔内由分组处理装置接收来自任何竞争数据源的竞争分组的干扰概率(interference probability)；(b)从这些参数得到损失概率的测量度，损失概率是数据分组中的信息丢失且未被纠错处理恢复的概率，其中损失概率的测量度是由用于评估(account for)由于缓存已满而引起的损失的处理推导得出，以及其中有以下任意一种情形：(1)该处理具有独立于缓存大小的计算复杂度，对于到达概率、发送概率和干扰概率的所有值都从0到1的情形，损失概率的值从0到1，或者(2)该处理代表了如下模型的解(solution)，在该模型中，源信号中的分组根据确定性过程(deterministic process)到达分组处理装置；和(c)响应于损失概率的测量度调整第一数目或第二数目。

本发明的另一方面控制通信系统中的分组供应，该通信系统包括：第一数据源，提供携带布置在一组分组中的信息的源信号；分组处理装置，接收源信号，将该组分组中的至少一些分组的信息保存在有缓存大小的缓存中，以及发送包括如下信息的分组的输出信号，即，所述信息中的至少一些被保存在缓存中，其中在该组分组中的至少一些分组的信息由于缓存已满引起的损失而从输出信号中被遗漏；和接收器，接收在输出信号中的至少一些分组。该控制得以实现是通过(a)接收一个或多个携带参数的信号，所述参数表示缓存大小、在时间间隔内由分组处理装置从任何竞争数据源接收到竞争分组的干扰概率和当缓存非空时分组处理装置在时间间隔内成功发送的分组的发送概率；(b)从这些参数为多个到达概率中的每一个得出相应损失概率，其中每一相依损失概率表示数据分组中的信息被丢失的概率，它由用于评估由缓存已满引起的损失的处理得出，其中每一到达概率表示由分组处理装置在时间间隔内从第一数据源接收到分组的概率，其中有以下情形中的任意一种：(1)该处理具有独立于缓存大小的计算复杂度，以及对于到达概率、发送概率和干扰概率的所有值都从0到1的情形，损失概率的值从0到1，或(2)该处理代表了模型的解，在该模型中，源信号中的分组根据确定性过程到达分组处理装置；(c)选取如下到达概率，根据该到达概率得出多个损失概率中的最小损失概率；(d)调整第一数据源的操作，以使得分组处理装置以更接近地反映所选取的到达概率的方式接收分组。

参考以下讨论和附图，本发明的各种特征及其优选实施例能被更好地理解。以下讨论的内容和附图仅是示例性的，不应被理解为表示对本发明范围的限制。

附图说明

图1是通信系统的示意图。

图2-4是根据CBR业务模型布置在时隙中的各组主要分组的示意图。

图5-7是根据缓存占用状态的稳态概率的图解说明。

具体实施方式

A.介绍

1.通信系统

图1是通信系统的示意图，在其中有一个或多个提供源信号的数据源2、4，源信号携带被布置在分组中的信息。例如，在至少一些分组中携带的信息可以是多媒体信息。由数据源2提供的源信号携带被布置在被称为“主要分组”的各组分组中的信息，因为这些分组的维护(servicing)是本发明的目的。主要分组的组包括主要数据分组和主要纠错(error-correction，EC)分组。一组包括k个主要数据分组和(n-k)个主要EC分组，其中一组中一共有n个主要分组。其他数据源，如数据源4，也提供携带被被布置在被称为“竞争分组”的分组中的信息的源信号，因为这些后者分组竞争提供主要分组所需的资源；然而，来自这些其他数据源的源信号不需要携带同样类型的信息，并且竞争分组也不需要以与针对数据源2描述的相同方式被布置。

来自数据源2、4中的每个的源信号分别沿通信通道3、5被传递到分组处理装置10。这些通信通道3、5可以由各种各样的媒体来实现，包括例如金属线和光纤。分组处理装置10从数据源2、4中的每个接收分组，并将至少一些分组的信息存储在队列或缓存中。分组处理装置10沿着通信通道11将信息分组发送给接收机20。在如该图所示的例子中，接收机20处理来自数据源2、4的信息分组。它对从数据源2接收到的信息的主要分组应用所需的EC处理，并将结果信息沿通信通道21传递。它将来自数据源4的信息的竞争分组沿通信通道22传递。根据需要，通信系统可能包括其他接收机、发射机和数据源。

该通信系统可以与其他技术相结合，例如服务质量(quality-of-service)处理或附加的EC处理。服务质量处理可用于防止或减少所有分组损失。对于主要分组，这例如可以通过使数据源2或分组处理装置10重传那些接收机20未确认接收的主要分组而得以完成。除了上面提到、下面将讨论的EC处理外，一个或多个EC处理也可以被使用。这些附加的EC处理可以在分组处理装置10和接收机20中实现以减少I类损失。附加处理的结合会降低能通过通信通道11发送原始分组的速率，因为需要一些通道带宽用于重传分组和传输第二EC处理的附加EC分组。因此，I类损失的概率会相应的增加。服务质量和附加EC处理并不包括在以下将要讨论的通信模型中，但如果需要可以被结合在其中。

如图1所示的示意图没有包括一些实际实现通信系统所需要的、但对于解释本发明是不需要的部件。例如，该图未示出用于确定通信通道11是否是畅通的(clear)的必要部件，即，其他分组处理装置是否正使用通信通道11或是否存在一些类型的干扰可能阻止接收机20的接收。也未示出从接收机20获取任何关于分组损失或需要重传分组的信息所需要的部件。

2.通信系统模型

本发明各个方面的执行都是基于使用从通信系统的模型推导得出的算法对II类损失概率的计算的。所述模型根据以下将要描述的几个参数推导得出II类主要分组损失。这些参数中的每一个都影响缓存占有率的等级，缓存占有率的等级又影响II类损失的概率。

通信系统的模型要考虑EC参数(n，k)的变化如何影响主要数据分组速率，因此允许设计自适应EC系统以使II类主要分组损失最小化。在以下描述的推导中，该方法考虑在分组处理系统装置10处所有分组的到达模式(pattern)、在分组处理装置10中的缓存大小和通信通道11的可用性(availability)。然后，该模型被用于导出能计算II类主要分组损失概率的算法，并调整EC参数(n，k)以使通过EC处理的错误恢复主要数据分组的损失最小化。

以下描述的通信模型假设除了在上提到的自适应EC处理以外，没有使用任何处理来减轻II类损失。未包括在该模型中的处理的一个例子是服务质量保护处理，在该服务质量保护处理中数据源2再一次发送接收机20未确认接收的任何主要分组。接收机20对于其接收到的分组而向数据源2发送确认。如果数据源2在某一段时间内未接收到确认，它再一次发送一个或多个认为丢失了的主要分组。该处理减轻I类和II类损失。在该模型中包括这样的处理可能要考虑到这样的事实：多于一次的发送主要分组增加了在分组处理装置10处主要分组到达的速率，这增加了缓存占有率和增加了II类损失率。再次发送分组的频率反过来取决于损失概率。

a)基本方法

如下所述，开发和解决了两个基于马尔可夫的(Markov-based)稳态模型，其将缓存占有率描述为以下参数的函数：(1)从数据源2到达分组处理装置10的主要分组的速率，(2)从其他数据源到达分组处理装置10的竞争分组的速率，(3)由分组处理装置10发送、接收机20无损坏接收的主要分组的概率，(4)在分组处理装置10中缓存或队列的大小，和(5)EC参数(n，k)。这些模型中的一个描述了一种系统，在该系统中主要分组根据具有符合柏努利过程(Bernoulli process)的概率分布的概率过程而达到分组处理装置10。另一个模型描述了一种系统，在该系统中主要分组根据符合固定比特率(constant bit rate，CBR)过程的确定性过程达到分组处理装置10。如果不使用EC处理，这些模型中的每一个用于都作为缓存占有率的函数，为由数据源2提供的主要分组集合中的任一单个数据分组计算II类损失概率。如果使用EC处理，EC恢复后的主要数据分组损失的概率作为EC参数(n，k)的函数被计算。

对这两个模型的数学分析非常不同。对于CBR业务，奇异值分解被用于解决稳态马尔可夫模型(参见Press et al.，Numerical Recipes in C++：TheArt of Scientific Computing，2nd ed.，Cambridge University Press，1992.)。对于柏努利分布(bernoulli-distributed)业务，应用线性递归方程(linearrecurrent equation)为马尔可夫模型建立封闭形式解(closed-form solution)。并且，对于两种业务，EC恢复后的分组损失概率的计算也不同。对于柏努利分布业务，假设数据分组和EC分组的到达是统计上独立的，这使得简单组合变量的应用能确定分组损失概率。对于CBR业务，开发出以迭代数学过程，其反映数据和EC分组的准确到达模式。对于每一模型，竞争分组的业务被假设为柏努利分布。这是稳妥的假设，因为它隐含了数据源2和接收机20不知道对竞争分组的实际过程。由于对由数据源2发送的主要分组的到达过程是已知的并且是可被控制的，然而，对该业务不同处理的影响能被研究。

本发明可被有利地用于通信系统，在该通信系统中分组处理装置10采用无线频率(RF)或其他无线技术用于通信通道11来发送对多媒体分组；然而，本发明并不限于数据分组的任何特定类型或任何特定的通信技术。无线通信通道影响以下模型的唯一特性是对于主要分组未被成功发送或接收的感知概率的允许性。有线或光学技术通过将该概率减小为0或减小为某些任意小的值也能替代地模型化。

b)导出概述

以下部分描述了一般(generic)通信模型，推导得出计算单独分组的损失概率的一般算法，为柏努利-分布业务得出分析的通信模型，为CBR业务推导得出通信模型，并为每一模型计算EC恢复后的损失概率。由于用于计算CBR业务损失概率的算法是计算复杂的，推导得出一种计算损失概率近似值的算法，该算法复杂性大为降低。

B.通信系统模型

1.概述

以下讨论的两个通信模型描述了如图1所示的系统的通信系统的操作。模型允许除了接收机20外的一个或多个接收机存在。根据这些模型，分组处理装置10从数据源接收分组，并将它们保存在缓存中。分组随后被从缓存中取出，并沿通信通道11被发送。模型假设分组以先进先出(FIFO)的顺序被保存和从缓存中取出。如果分组到达时缓存已满，该分组将被丢弃。以下描述的技术可以推导得出能容纳其他队列策略、但数学分析更复杂的模型。

以下讨论的模型是时间离散模型，在该模型中分组处理装置10在被称为时隙的一致时间间隔内接收和发送分组。为了简化该模型，所有分组都是相同的固定大小。

模型假设在任何给定的时隙中分组处理装置10能接收主要分组和竞争分组，并且能发送分组。这个假设简化了计算；然而，如果想得出更一般的模型，可以放宽该假设。“柏努利-业务模型”描述了一个通信系统，在该通信系统中主要分组以能被具有柏努利概率分布的概率过程来描述的方式到达分组处理装置10。这些分组中的其中之一在任何给定时隙内到达分组处理装置10的概率由符号p_A表示，其中0≤p_A≤1。“CBR-业务模型”描述了一个通信系统，在该通信系统中主要分组以可由确定性过程描述的方式到达分组处理装置10，在该确定性过程中分组以每m个时隙一次的固定速率到达。为了便于讨论，比例也被称为到达概率并用符号p_A表示。由于假设分组携带固定量的信息或固定数目的比特，固定分组到达率等于固定比特率(CBR)；因此第二模型被称为CRB-业务模型。

两个模型都假设：由除数据源2外的其他数据源提供的所有竞争分组都以能被具有柏努利概率分布的概率过程描述的方式到达分组处理装置10。竞争分组在给定时隙内到达分组处理装置10的概率由符号p_C表示，其中0≤p_C≤1。该假设对大多数应用都是合理的，因为由其他数据源用于发送竞争分组的处理一般是未知的。可采用任何能用于测量或估计竞争分组到达的技术来推导得出竞争分组到达过程的分布，以下描述的技术可用于构造一个反映到达过程的模型。然而，如果到达过程是未知的，柏努利分布是一个适当的假设。由于以下描述的模型仅对所有竞争分组的累积到达概率p_C感兴趣，因此这些模型假设仅有一个用于竞争业务的数据源存在。这一个源可以代表多个数据源的累积影响。

两个模型还假设，对于在其中至少一个分组被保存到缓存中的每一时隙，分组处理装置10成功地从缓存中检取一个分组并把该分组以由符号p_D表示的概率通过通信通道11进行发送，其中0≤p_D≤1。如果一个分组携带的信息被接收机20无损坏的接收到了，则这个分组被认为已被成功发送。分组中的信息可能由于与由其他装置沿相同通信通道发送的其他分组冲突而被损坏，或由于噪声或其他干扰而被损坏。在优选执行中，通过使分组处理装置10在尝试发送分组前确定通信通道11是否是畅通的来减少冲突的风险。

根据分组所携带的信息的特殊应用，被损坏的信息也许有用、也许没用。例如，仅是部分损坏的视频帧中的损坏视频信息在一些例子中可以被基于未损坏视频信息的预测所代替(参见Wah et al.，”A Survey ofError-Concealment Schemes for Real-Time Multimedia and VideoTransmissions over the Internet”，IEEE Int.Symposium on MultimediaSoftware Eng.2000，Taipei，Taiwan.)。相对于这个例子，在携带高度压缩音频信息的损坏分组中恢复或替代信息是不可能的。以下描述的模型假设部分被损坏的分组不包含任何有用的信息，并使用分组被无损坏发送到接收机20的概率p_D。如果需要，通过定义由接收机20接收的部分被破坏的分组的附加概率，损坏分组能被至少部分恢复的概率可被结合到该模型中。采用通信通道11的吉尔伯特模型(Gilbert model)可以从该附加概率推导得出一个适当的概率p_D(参见Bolot et al.，”Adaptive FEC-based error control for Internettelephony”，IEEE Infocom 2003，San Francisco.)。

在有多个竞争数据源的系统中，可能在一个时隙中平均多于一个竞争分组能到达，这可以用关系p_C＞1来表达。为了简化计算，以下模型假设0≤p_C，p_A，p_D≤1。通过减小每一时隙的长度以使p_C，p_A，p_D＜1，能实现该假设。

以下描述的模型和随后的导出考虑了分组损失，而没有考虑延迟和延迟抖动。并且，模型考虑了仅从数据源流向接收机的分组业务，而没有考虑从接收机流向数据源的信号。

2.缓存操作的分析

以下描述的模型假设分组处理装置10具有长度为L的队列或缓存，并且在每一时隙，该装置尝试在该缓存中保存从数据源2接收到的任何主要分组和从其他数据源接收到的任何竞争分组。根据这些模型，由该装置完成的将分组保存到缓存中的操作可被描述如下：

1.在任何给定时隙，该装置以概率p_A从数据源2接收主要分组和以概率p_C从其他源接收竞争分组。如果在相同时隙接收到主要分组和竞争分组，假设两个分组中的其中任何一个比另一个先到达的概率是相同的。换句话说，假设竞争分组比主要分组先到的概率等于0.5。

2.在给定时隙中能到达的主要分组和竞争分组的总数j可以是在组{0，1，2}中的任何数。根据以下规则，到达的分组可能被保存在缓存中或可能被丢弃：

a)如果缓存占有率的等级恰在这些分组的到达之前小于或等于L-j，则所有到达的分组都被保存到缓存中。

b)如果j＝2且缓存占有率的等级为L-1，则两个到达分组中较早的那个被保存在缓存中，而较晚到达的分组被丢弃。

c)否则，所有到达的分组都被丢弃。

3.在任何给定时隙，分组处理装置10以概率p_D从缓存中检取分组，并将分组沿通信通道11发送，以使该分组携带的信息能无损坏的被接收。分组以FIFO的顺序被存入缓存和从缓存检取。如果缓存是空的，不检取和发送分组。如果一个分组被检取并被发送，则缓存占有率的等级减1。

以下描述的模型包括一稳态矢量，它描述缓存的统计占有率。该矢量被表达为：

P＝(P_N)，其中0≤N≤L    (1)

其中P_N＝在时隙结束时在缓存中保存N个分组的概率；且

L＝缓存的大小或长度。

该稳态矢量可以表达为参数p_A、p_C、p_D和L的函数。以下将导出该函数的表达式。

C.分组损失概率

1.介绍

如果在主要分组到达分组处理装置10的时隙期间，存在两种情况中的一种，来自数据源2的主要分组将被分组处理装置10丢弃：(1)缓存占有率为L或者(2)缓存占有率为L-1且竞争分组比主要分组先到达。在给定时隙中到达的主要数据分组将被丢弃的概率P_loss可被表达为：

$P_{\mathrm{loss}}=\frac{1}{2}{P}_{L-1}{p}_C+P_L---\left(2\right)$

系数二分之一反映了当主要分组和竞争分组在相同时隙到达时，竞争分组比主要分组先到达的概率等于0.5的假设。

稳态矢量P可以从转移矩阵(transition matrix)计算得到，该转移矩阵的项(entry)代表了在P的不同状态间转换的概率。转移矩阵的通用参数表达式被首先开发。然后通过对参数做适当的选择就能将该通用表达式适用于柏努利-业务和CBR-业务模型。

2.转移矩阵

转移矩阵用符号T表示，符号T_a，b被用于表示缓存占有率等级在连续时隙间从a变化到b的概率，其中0≤a，b≤L。在从缓存中移出(remove)任何所发送的分组后的每一时隙结束时测量缓存占有率的等级。符号(T_a，b)^u被用于表示缓存占有率的等级经过u个时隙从a变化到b的概率，其中u≥1；因此T_a，b＝(T_a，b)¹。

可以如下表达转移矩阵中的元素：

其中q_A＝在时隙中没有主要分组到达的概率，或者q_A＝1-p_A；

q_C＝在时隙中没有竞争分组到达的概率，或者q_C＝1-p_C；

q_D＝在时隙中未成功发送数据分组的概率，或者q_D＝1-p_D。

在尝试发送失败、没有尝试发送和作为服务质量保护处理的一部分重传分组的那些时隙中数据分组未成功发送。

例如，项T_0，0代表了假设在一时隙结束时缓存是空的，在下一时隙结束时该缓存仍然是空的的概率。这种情况可以由三种可能的情况引起，这三种可能的情况的概率由在表达式3中所示的T_0，0的三个项中的每一个所表达。第一项q_Aq_C表示在下一时隙中没有主要分组和竞争分组到达的概率。第二项q_Ap_Cp_D表示没有主要分组达到、竞争分组到达并被保存在缓存中和从缓存中取出分组并发送的概率。第三项p_Aq_Cp_D表示主要分组到达并被保存在缓存中、没有竞争分组到达和从缓存中移除分组并发送的概率。

D.柏努利-业务II类分组损失的概率

用于计算无EC保护的柏努利分布业务II类分组损失概率的模型被首先开发。该模型然后被修改以计算有EC保护的柏努利分布业务分组损失的概率。

1.无EC保护的柏努利-分布业务的稳态模型

开发柏努利-业务模型的第一步是推导无EC保护的柏努利-分布业务模型的稳态矢量P的计算。在许多马尔可夫模型的应用中，为稳态矢量P推导得出精确的公式是不可能的，但该矢量可以表达为矩阵分解的奇异值分解的结果。不幸的是，该方法并没有吸引力，因为它的解决方案不是封闭形式的并且计算非常复杂。然而，线性迭代公式理论被用于为P建立封闭形式的表达式。通过首先在定理1为P推导得出一个相当复杂和计算花费大的公式，该公式将在定理2中被简化。

定理1的证明如下。

定理1

$P_0=\frac{1}{1+\underset{j=1}{\overset{L-1}{\Sigma }}\frac{W^j}{Y^j}{B}_j+\frac{Z}{p_D}}---\left(4\right)$

$P_j=P_0\frac{W^j}{Y^j}{B}_j,L-1\ge j\ge 1---\left(5\right)$

$P_L=\frac{P_0}{p_D}Z---\left(6\right)$

其中$B_j=\underset{l=0}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-l\\ l\end{array}\right),1\le j\le L-1---\left(7\right)$

W＝p_Ap_C+q_Ap_Cq_D+p_Aq_Cq_D    (8)

X＝p_Ap_Cq_D    (9)

Y＝q_Aq_Cp_D    (10)

$Z=(1+Y-p_D-q_A{q}_C{q}_D)\frac{W^{L-1}}{Y^{L-1}}{B}_{L-1}-(W-X)\frac{W^{L-1}}{Y^{L-2}}{B}_{L-2}-X\frac{W^{L-3}}{Y^{L-3}}{B}_{L-3}---\left(11\right)$

通过归纳法证明定理1。从式3给出的转移矩阵定义，可以推导出以下关系：

P₀＝P₀(q_Aq_C+q_Ap_Cp_D+p_Aq_cp_D)+P₁q_Aq_Cp_D                               (12)

P₁＝P₁(q_Aq_Cq_D+q_Ap_Cp_D+p_Aq_cp_D)+P₀(p_Ap_Cp_D+p_Aq_cq_D+q_Ap_Cq_D)+P₂q_Aq_Cp_D    (13)

P_j＝P_j(q_Aq_Cq_D+q_Ap_Cp_D+p_Aq_cp_D)+P_j-1(p_Ap_Cp_D+p_Aq_cq_D+q_Ap_Cq_D)+

    P_j+1q_Aq_Cp_D+P_j-2p_Ap_Cq_D，2≤j≤L-2                              (14)

P_L-1＝P_L-1(q_Aq_Cq_D+q_Ap_Cp_D+p_Aq_cp_D+p_Ap_Cp_D)+

      P_Lp_D+P_L-2(p_Ap_Cp_D+p_Aq_cq_D+q_Ap_Cq_D)+P_L-3p_Ap_Cq_D                  (15)

P_L＝P_Lq_D+P_L-1(p_Aq_Cq_D+q_Ap_Cq_D+p_Ap_Cq_D)+P_L-2p_Ap_Cq_D                    (16)

使用由表达式7至11给出的定义，在表达式12至15中给出的关系可表示为：

P₁Y＝P₀W                                                           (17)

P₂Y＝P₁(W+Y)-P₀(W-X)                                               (18)

P_j+3Y＝P_j+2(W+Y)-P_j+1(W-X)-P_jX，0≤j≤L-4                          (19)

P_Lp_D＝P_L-1(1+Y-p_D-q_Aq_Cq_D)-P_L-2(W-X)-P_L-3X                          (20)

在等式17、18和19中给出的关系意味着在等式5中j＝1，2，3时的关系。假设等式19的取值为j、j+1和j+2，则它也能被用于表示取值为4≤j+3≤L-1的等式5。使用在等式5中给出的定义改写等式19中的关系，可以看出通过证明以下等式能证明定理1：

$Y\frac{W^{j+3}}{Y^{j+3}}{B}_{j+3}=(W+Y)\frac{W^{j+2}}{Y^{j+2}}{B}_{j+2}-(W-X)\frac{W^{j+1}}{Y^{j+1}}{B}_{j+1}-X\frac{W^j}{Y^j}{B}_j---\left(21\right)$

它等价于

W³B_j+3＝W³B_j+2+W²YB_j+2-W²YB_j+1+WXYB_j+1-XY²B_j     (22)

其可被重新安排为：

W³B_j+3-W³B_j+2-WXYB_j+1＝W²YB_j+2-W²YB_j+1-XY²B_j     (23)

已知：

$\left(\begin{array}{c}i+1\\ j\end{array}\right)=\left(\begin{array}{c}i\\ j\end{array}\right)+\left(\begin{array}{c}i\\ j-1\end{array}\right)---\left(24\right)$

$\left(\begin{array}{c}i\\ 0\end{array}\right)=0---\left(25\right)$

其中表示等于可从i种可能性中选取无顺序的j个结果的方法数的二项式系数。

使用等式7中的表达式，等式23左手侧的项能被改写为以下形式：

$W^3{B}_{j+3}{=W}^3\underset{l=0}{\overset{\frac{j+3}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+3-l\\ l\end{array}\right)---\left(26\right)$

$W^3{B}_{j+2}{=W}^3\underset{l=0}{\overset{\frac{j+2}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+2-l\\ l\end{array}\right)---\left(27\right)$

${\mathrm{WXYB}}_{j+1}=\mathrm{WXY}\underset{l=0}{\overset{\frac{j+1}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+1-l\\ l\end{array}\right)=W^3\underset{l=1}{\overset{\frac{j+3}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+1-(l-1)\\ l-1\end{array}\right)---\left(28\right)$

通过将该关系应用于等式24和25中，并且合并和简化这些项，等式23左手侧如下所示等于零：

$W^3{B}_{j+3}-W^3{B}_{j+2}-{\mathrm{WXYB}}_{j+1}=$

$A^3\underset{l=1}{\overset{\frac{j+2}{2}}{\Sigma }}{\left(\frac{\mathrm{BC}}{A^2}\right)}^l[\left(\begin{array}{c}j+3-l\\ l\end{array}\right)-\left(\begin{array}{c}j+2-l\\ l\end{array}\right)-\left(\begin{array}{c}j+2-l\\ l-1\end{array}\right)]+$

$A^3(\left(\begin{array}{c}j+3\\ 0\end{array}\right)-\left(\begin{array}{c}j+2\\ 0\end{array}\right))+A^3\underset{l>\frac{j+2}{2}}{\overset{\frac{j+3}{2}}{\Sigma }}{\left(\frac{\mathrm{BC}}{A^2}\right)}^{l-1}[\left(\begin{array}{c}j+3-l\\ l\end{array}\right)-\left(\begin{array}{c}j+1-(l-1)\\ l-1\end{array}\right)]=0---\left(29\right)$

等式23右手侧的项可被表示为如下形式：

$W^2{\mathrm{YB}}_{j+2}=W^{2}Y\underset{l=0}{\overset{\frac{j+2}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+2-l\\ l\end{array}\right)---\left(30\right)$

$W^2{\mathrm{YB}}_{j+1}=W^{2}Y\underset{l=0}{\overset{\frac{j+1}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+1-l\\ l\end{array}\right)---\left(31\right)$

${\mathrm{XY}}^2{B}_j=W^{2}Y\underset{l=0}{\overset{\frac{j+2}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-(l-1)\\ l-1\end{array}\right)---\left(32\right)$

通过将该关系应用于等式24和25，并且合并和简化这些项，等式23右手侧如下所示等于零：

$W^2{\mathrm{YB}}_{j+2}-W^2{\mathrm{YB}}_{j+1}-{\mathrm{XY}}^2{B}_j=$

$W^{2}Y\underset{l=0}{\overset{\frac{j+1}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l[\left(\begin{array}{c}j+2-l\\ l\end{array}\right)-\left(\begin{array}{c}j+1-l\\ l\end{array}\right)-\left(\begin{array}{c}j+1-l\\ l-1\end{array}\right)]-$

$W^{2}Y{\left(\frac{\mathrm{XY}}{W^2}\right)}^l(\left(\begin{array}{c}j+2\\ 0\end{array}\right)-\left(\begin{array}{c}j+1\\ 0\end{array}\right))-$

$W^{2}Y\underset{l>\frac{j+1}{2}}{\overset{\frac{j+2}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l[\left(\begin{array}{c}j+2-l\\ l\end{array}\right)-\left(\begin{array}{c}j+1-l\\ l-1\end{array}\right)]=0---\left(33\right)$

根据等式23、29和33可以得出对于j+3等式5为真(true)。对于j＝L，根据等式5和20可以得出等式6。根据等式5和6及$\underset{j=0}{\overset{L}{\Sigma }}{P}_j=1$可以得出等式4。

为定理1中的B_j推导得出的表达式可以通过定义B₀＝1如在等式7中所示的那样扩展B_j的定义得以简化。实现如下所示：

引理1

$B_{j+1}{=B}_j+\left(\frac{\mathrm{XY}}{W^2}\right)B_{j-1},j\ge 1---\left(34\right)$

等式34中的关系等价于：

$\left(\begin{array}{c}j+1\\ 0\end{array}\right)+\underset{l=1}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+1-l\\ l\end{array}\right)+\underset{l>\frac{l}{2}}{\overset{\frac{j+1}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+1-l\\ l\end{array}\right)=$

$\left(\begin{array}{c}j\\ 0\end{array}\right)+\underset{l=1}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-l\\ l\end{array}\right)+\underset{l=1}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-1\\ l-1\end{array}\right)+\underset{l>\frac{j}{2}}{\overset{\frac{j+1}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-1\\ l-1\end{array}\right)---\left(35\right)$

从等式25可以看出在等式35左手侧的第一项与该等式右手侧的第一项都等于1。从等式24可以看出等式35左手侧的第二项等于该等式右手侧的第二项和第三项的和，如等式36所示：

$\underset{l=1}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j+1-l\\ l\end{array}\right)=\underset{l=1}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-1\\ l\end{array}\right)+\underset{l=1}{\overset{\frac{j}{2}}{\Sigma }}{\left(\frac{\mathrm{XY}}{W^2}\right)}^l\left(\begin{array}{c}j-1\\ l-1\end{array}\right)---\left(36\right)$

根据检验(inspection)，可以看出，如果求和项不在l＝1到¹/₂j的求和范围内，等式35左手侧的第三项和该等式35右手侧的第四项都等于0；如果该求和项在该求和范围内，则都等于1。这建立了引理1，引理1显示了项B_j可以被表达为广义Fibonacci数。

引理2

级数被定义为

x₀＝x₁＝1且x_i＝K_Ax_i-1+K_Bx_i-2，对于i≥2      (37)

其中K_A和K_B是正实数。

如果将α和β定义为等式x²＝K_Ax+K_B的根，或者

$\alpha =\frac{K_A+\sqrt{{{K_A}^2+4K}_B}}{2}$

$\beta =\frac{K_A+\sqrt{{{K_A}^2+4K}_B}}{2}$

且其被限制为互不相等，则根据线性迭代方程式的理论可知：

$x_i=\frac{1}{\sqrt{{K_A}^2+4K_B}}[(1-\beta ){\alpha }^i+(\alpha -1){\beta }^i]---\left(38\right)$

根据表达式37和38的检验可以看出对于i＝0，1等式38为真，通过归纳可以看出对于i≥2等式38为真。通过将如等式37所示的关系应用到等式34的B_j的表达式中，可得出K_A和K_B有如下值：

K_A＝1

$K_B=\frac{\mathrm{XY}}{W^2}$

可得出：

$\alpha =\frac{1+K_C}{2}$

$\beta =\frac{1-K_C}{2}$

其中$K_C=\sqrt{1+4\frac{\mathrm{XY}}{W^2}}---\left(39\right)$

这意味着β＝1-α。通过使用该关系代替等式38中的β，在等式7中所示的B_j的表达式可以被改写为

$B_j^{*}=\frac{1}{K_C}({\left(\frac{1+K_C}{2}\right)}^{j+1}-{\left(\frac{1-K_C}{2}\right)}^{j+1})=\frac{1}{K_C}\frac{{(1+K_C)}^{j+1}-{(1-K_C)}^{j+1}}{2^{j+1}}---\left(40\right)$

该式比等式7中的表达式计算复杂度小。

使用在等式39和40中的关系代替B_j和K_C，使等式4中的项可被改写为：

$\underset{j=1}{\overset{L-1}{\Sigma }}\frac{W^j}{Y^j}{B}_j^{*}=$

$\frac{W}{{\mathrm{YK}}_C}[{\left(\frac{1+K_C}{2}\right)}^2·\underset{j=0}{\overset{L-2}{\Sigma }}\frac{{\left(W(1+K_C)\right)}^j}{{\left(2Y\right)}^j}-{\left(\frac{1-K_C}{2}\right)}^2·\underset{j=0}{\overset{L-2}{\Sigma }}\frac{{\left(W(1-K_C)\right)}^j}{{\left(2Y\right)}^j}]=$

$\frac{W}{{\mathrm{YK}}_C}[{\left(\frac{1+K_C}{2}\right)}^2\left(\frac{\frac{{\left(W(1+K_C)\right)}^{L-1}}{{\left(2Y\right)}^{L-1}}-1}{\frac{W(1+K_C)}{2Y}-1}\right)-{\left(\frac{1-K_C}{2}\right)}^2\left(\frac{\frac{{\left(W(1-K_C)\right)}^{L-1}}{{\left(2Y\right)}^{L-1}}-1}{\frac{W(1-K_C)}{2Y}-1}\right)]---\left(41\right)$

通过将等式4、5和6改写为如下形式可以获得比在定理1中推导得出的算法计算复杂度小的、计算稳态矢量P的算法：

$P_0=\frac{1}{1+K_D+\frac{Z^{*}}{p_D}}---\left(42\right)$

$P_j=P_0\frac{W^j}{Y^j}{B}_j^{*},T-1\ge j\ge 1----\left(43\right)$

$P_T=\frac{P_0}{p_D}{Z}^{*}---\left(44\right)$

其中

$K_D=\frac{W}{{\mathrm{YK}}_C}[{\left(\frac{1+K_C}{2}\right)}^2\frac{\frac{{\left(W(1+K_C)\right)}^{L-1}}{{\left(2Y\right)}^{L-1}}-1}{\frac{W(1+K_C)}{2Y}-1}-{\left(\frac{1-K_C}{2}\right)}^2\frac{\frac{{\left(W(1-K_C)\right)}^{L-1}}{{\left(2Y\right)}^{L-1}}-1}{\frac{W(1-K_C)}{2Y}-1}]$

$B_j^{*}=\frac{{(1+K_C)}^{j+1}-{(1-K_C)}^{j+1}}{2^{j+1}{K}_C},1\le j\le L-1$

W＝p_Ap_C+q_Ap_Cq_D+p_Aq_Cq_D

X＝p_Ap_Cq_D

Y＝q_Aq_Cp_D

$Z^{*}=(1+Y-p_D-q_A{q}_C{q}_D)\frac{W^{L-1}}{Y^{L-1}}{B}_{L-1}^{*}-(W-X)\frac{W^{L-1}}{Y^{L-2}}{B}_{L-2}^{*}-X\frac{W^{L-3}}{Y^{L-3}}{B}_{L-3}^{*}$

2.柏努利-业务模型的分组损失概率

当不使用EC保护时，丢失任何一个主要分组的概率可以使用等式2和42至44计算。当为柏努利-分布业务使用EC保护时，假设丢失数据分组的概率独立于丢失EC分组的概率。附加的EC分组通过因素增加了主要分组的达到率。因此达到的概率由于同样的因素也被增加了，该概率可被表达为：

当使用EC保护时，如果i个数据分组丢失了且至少s＝(n-k-i+1)个EC分组也丢失了，主要数据分组将丢失且不能被恢复，其中i＞0和s＞0。无EC恢复的丢失数据分组概率可以通过在等式46中将接收i个主要数据分组的概率与接收至少s个主要EC分组的概率相乘计算得到：

$p_i(k,n)=\left(\begin{array}{c}k\\ i\end{array}\right){\left(P_{\mathrm{loss}}\right)}^i{(1-P_{\mathrm{loss}})}^{k-i}\underset{m=s}{\overset{n-k}{\Sigma }}\left(\begin{array}{c}n-k\\ m\end{array}\right){\left(P_{\mathrm{loss}}\right)}^m{(1-P_{\mathrm{loss}})}^{n-k-m}---\left(46\right)$

其中p_i(k，n)＝丢失i个数据分组和至少s个EC分组的概率；和

s＝max(0，n-k-i+1).

在等式46中示出的概率P_loss使用在等式45中示出的修改的p_A值，如在等式2中所示那样得以计算。P_loss现在表示主要数据分组或主要EC分组将被丢弃的概率。

无EC恢复地丢失主要数据分组的概率E_loss等于：

$E_{\mathrm{loss}}=\frac{1}{k}\underset{i=1}{\overset{k}{\Sigma }}i·p_i(k,n)---\left(47\right)$

EC恢复后的恢复主要数据分组的概率E_rec等于：

E_rec＝1-E_loss(48)

E.CBR-业务模型的II类分组损失概率

1.带EC的CBR-业务模型的发送方案

以上所示的计算稳态矢量P的算法是为通信系统的柏努利-业务模型推导的。以下章节推导计算通信系统的CBR-业务模型的矢量P的算法。在该模型中，时隙的编号从1到无穷大，且主要数据分组在时隙t＝m，2m，…中到达分组处理装置，其中m＞1。在m-1个中间时隙中没有主要数据分组到达。一组k个主要数据分组与一组(n-k)个主要EC分组结合形成一组n个主要分组。在图2中示出了一组m＝4，k＝3且n＝5的分组的例子。在第一组中的k个主要数据分组用标签D1表示，其在由k·m个时隙所隔开的间隔上的m时隙间中的每一中到达分组处理装置10一次。在下一组的主要数据分组用标签D2表示，其在下一由k·m个时隙所隔开的间隔期间以相同的方式到达。第一组的(n-k)个EC分组用标签EC1表示，其在下一组主要分组的数据分组之间的空闲(free)时隙中到达。为了保证该方案的可行性，限制EC参数(n-k)以使EC分组的数目(n-k)不超过下一k个数据分组空闲时隙的数目，这可被表达为：

n-k≤k·(m-1)(49)

该到达方案形式上可描述为：

$e_i=\left(\begin{array}{ccc}m,& 2\le i\le k& \\ 1,& i=k+1& \\ 1,& k+2\le i\le n,& t_i\ne 1\left(\mathrm{mod}m\right)\\ 2,& k+2\le i\le n,& t_i=1\left(\mathrm{mod}m\right)\end{array}\right)---\left(50\right)$

其中e_i＝t_i-t_i-1，2≤i≤n；和

t_i＝一组主要分组中的第i个分组到达分组处理装置10的时隙。

在表达式50中的第一行属于除了第一个主要数据分组以外的在一组主要分组中的所有数据分组。第二行属于一组中的第一个主要EC分组，该EC分组紧跟在这组中最后一个数据分组的后面。第三行属于不紧跟在下一组分组中的数据分组后的主要EC分组，最后一行属于那些紧跟在下一组分组的数据分组后的主要EC分组。

以下推导出的CBR-业务模型假设分组处理装置10从一组主要分组中将第一个分组丢弃，该第一个分组总是主要数据分组。以该分组丢弃的概率独立于任何之前主要分组被丢弃的概率的方式丢弃该分组。对于所有在该组主要分组中的随后的分组，主要分组被丢弃的概率使用之前主要分组的损失概率和之前主要分组到达处理装置10时的缓存占有率等级得以迭代地(iteratively)计算。该迭代方法与在等式2中所示的表达式一致，该等式表达了如下事实：只要当主要分组被丢弃是，缓存占有率的等级就至少是L-1。与在前分组未被丢弃且缓存占有率处于在0和L-1之间的较低等级的情况相比较，当在前主要分组到达时占有率等级至少为L-1的情况增加了当下一主要分组到达时占有率等级将至少为L-1的概率。因此，分组处理装置10是否丢弃在前主要分组提供了一些关于缓存占有率等级的信息，该信息反过来提供了一些关于下一主要分组将被丢弃的信息。

2.CBR-业务模型的转移矩阵

以上为柏努利-业务模型描述的转移矩阵在此为CBR-业务模型被调整。对于柏努利-分布业务，对于所有时隙到达过程是统计相等的，因为该处理仅取决于到达概率p_A。因此，上述的转移矩阵T能很好的描述任何两个相继时隙间的概率转换。对于CBR业务，平均或复合到达概率为$p_A=\frac{1}{m};$然而，对于CBR业务的到达过程是确定性的，每一时隙可被放置到两类中的一类。当时隙i＝1(mod m)时，主要分组到达，且对于这些时隙的转移矩阵F可以通过将表达式3中的p_A用值1代替、q_A用值0代替来获取。当时隙i≠1(modm)时，没有主要分组达到，且对于这些时隙的转移矩阵G可以通过将表达式3中的p_A用值0代替、q_A用值1代替来获取。转移矩阵F和G的乘积(product)指定了一系列时隙中分组的到达。有分组到达的每一时隙被F矩阵代表，没有分组到达的每一时隙被G矩阵代表。

3.无EC保护的CBR-业务模型的分组损失概率

在无EC保护的CBR-业务模型中的缓存占有率的稳态矢量π可被表达为以下形式：

π＝(FG^m-1)^Tπ         (51)

其中T代表了矩阵乘积的转置(transposition)。

等式51可通过矩阵(FG^m-1)^T-I的奇异值分解得以求解，其中I时所有对角项都为1的对角矩阵，从而获取一维的解空间，并使用等式

$\underset{i=0}{\overset{L}{\Sigma }}{\pi }_i=1---\left(52\right)$

来为π确定最终值。使用稳态矢量π而不是使用稳态矢量P，主要数据分组的损失概率可以由类似等式2的方程计算得出：

$P_{\mathrm{loss}}=\frac{1}{2}{\pi }_{L-1}{p}_C+{\pi }_L---\left(53\right)$

4.有EC保护的CBR-业务模型的分组损失概率

用于推导计算无EC保护的CBR-业务模型的分组损失概率方程式的方法可以被扩展，以为有EC保护的CBR-业务模型推导方程式。这通过计算一组k个数据分组的任一主要数据分组无法被恢复的概率得以完成。

a)主要分组的发送方案定义

在一组分组的n个主要分组中第一个被丢失的概率可以由紧接在第一个主要数据分组到达的时隙之前的那个时隙的缓存占有率的稳态矢量S确定。该稳态矢量是为在其期间一组主要分组中的k个数据分组到达的m·k时隙的集合而推导得出的。之前的一组主要分组的(n-k)个EC分组在第一w个时隙期间到达，其中

如果m≤w，则当前主要分组集合的一些数据分组在第一w个时隙期间也到达了。从等式49，可以看出w≤m·k。

附加值的定义如下：

u＝w(mod m) (55)

z＝m-u      (56)

f＝min(u，1)(57)

$y=\frac{k·m-w-f·z}{m}---\left(58\right)$

值z-1等于考虑的k·m个时隙的第w个时隙与下一主要数据分组之间的时隙数。值y等于在其间没有中间EC分组的m个时隙的周期数或循环数。稳态S根据这些值能得以表达。表达式62描述了如图3所示当m-1＞w的情况，其中m＝4，k＝4，n＝6，w＝2，u＝2，z＝2，f＝1且y＝3。表达式63描述了如图4所示当m-1＜w的情况，其中m＝4，k＝4，n＝8，w＝5，u＝1，z＝3，f＝1且y＝2。不需要m-1＝w时的表达式，因为对于所有m≥2的值w与m-1(mod m)不同余。这可以通过对m＝2时进行验证而得到。当m＝2时，w一定是偶数且与m-1(mod m)不同余。对于m＞2，该不同余可借助于假设相反通过反证法得以证明，即，通过假设存在值(n-k)以使

通过定义

其中0≤d≤m-2，其结合表达式59意味着

$n-k-r·(m-1)=\frac{d-m+1}{m}---\left(61\right)$

如等式61所示的表达式不可能为真，因为左手侧是整数而右侧不可能是整数。这与在等式59中表达的假设矛盾，这意味着w与m-1(mod m)不同余。

通过以上描述的到达过程的定义，稳态矢量S可被表达为：

S＝(F^w-m+1(G^z-1F)^f(G^m-1F)^yF^m-1)^TS    for m-1＜w    (62)

S＝(F(G^m-1F)^yF^wG^z-1)^TS               for m-1＞w    (63)

稳态矢量S可以通过把等式52中的π替代为S采用与从等式51中推导得出矢量π同样的方式得以确定。

b)EC恢复概率

在CBR-业务模型中使用EC处理恢复被丢弃数据分组的概率的计算可以由以下五个步骤中解释的那样得以计算。

步骤1：该步骤确定假设在时隙j结束时缓存占有率的等级为g的情况下，在时隙j+m-1结束时缓存占有率的等级为h的条件概率。该概率U(m-1，g，h)可被表达为

$U(m-1,g,h)=F^{x_1}{G}^{x_2}{F}^{x_3}{G}^{x_4}...F^{x_v},$对于0≤g，h≤L    (64)

其中x_j为正整数，且

$\underset{j=1}{\overset{v}{\Sigma }}{x}_j=m-1.$

条件概率的定义表达了如下事实：在m-1个中间时隙之间有一些在其中主要分组到达的时隙，由F矩阵表示，还有一些在其中没有主要分组到达的时隙，由G矩阵表示。特别地，假设在当第(j-1)个数据分组到达时的时隙结束时缓存占有率为g的情况下，在第j个主要分组到达前的时隙结束时缓存占有率为h的条件概率R(e_j-1，g，h)在2≤j≤n时得以计算。

其中(F^x)_g，h＝矩阵F升到第x次幂的第g行第h列的项；

(G^y)_g，h＝矩阵G升到第y次幂的第g行第h列的项；

(F^xG^y)_g，h＝矩阵乘积F^xG^y的第g行第h列的项；且

${\delta }_{g,h}=\left(\begin{array}{cc}1,& g=h\\ 0& g\ne h\end{array}\right)$

由于项R(e_j-1，g，h)仅为2≤j≤n时定义，任何使j超出该区间的参数组w、m、q和u表示不会发生的情况，应当被忽略。

步骤2：该步骤确定如果紧在主要分组到达时隙之前的时隙结束时缓存占有率的等级为h，到达的主要分组被丢弃或不被丢弃的条件概率。在以下情况下分组不会被丢弃：

●如果h≤L-2或者h＝L-1且k＝L-2，到达的分组不会被丢弃。

●如果h＝r＝L-1，其中r是在主要分组到达的时隙结束时的缓存占有率，如果两种情况中的任一中为真，则到达的分组不会被丢弃：没有竞争分组到达且以概率q_Cp_D从缓存中发送分组，或竞争分组到达但它是在主要分组之后到达的，且以概率从缓存中发送分组。

●如果h＝L-1且r＝L，其中r是在主要分组到达的时隙结束时的缓存占有率，如果两种情况中的任一中为真，则到达的分组不会被丢弃：没有竞争分组到达且没有以概率q_Cq_D从缓存中发送分组，或竞争分组到达但它是在主要分组之后到达的，且没有以概率从缓存中发送分组。

●如果h＝L，达到的主要分组被丢弃。

假设在当前时隙中主要分组到达，并且假设在上一时隙结束时缓存的占有率为h，在当前时隙结束时缓存占有率等于r且到达的主要分组不会被丢弃的条件概率可表达为：

类似地，假设在当前时隙中主要分组到达，并且假设在上一时隙结束时缓存的占有率为h，在当前时隙结束时缓存占有率等于r且到达的主要分组被丢弃的条件概率可表达为：

步骤3：该步骤确定假设在分组集合中的第(j-1)个主要分组到达的时隙结束时缓存的占有率为g的情况下，主要分组集合中第j个分组到达的时隙结束时缓存的占有率为r且第j个主要分组不被丢弃的条件概率。该条件概率可被表达为

$A(g,r,j)=\underset{h=0}{\overset{L}{\Sigma }}R(e_j-1,g,h)E_{h,r},\mathrm{for},0\le g,r\le L,2\le j\le n---\left(68\right)$

类似地，假设在分组集合中的第(j-1)个主要分组到达的时隙结束时缓存的占有率为g的情况下，主要分组组中第j个分组到达的时隙结束时缓存的占有率为r且第j个主要分组被丢弃的条件概率可被表达为：

$B(g,r,j)=\underset{h=0}{\overset{L}{\Sigma }}R(e_j-1,g,h)E_{h,r}^{*},\mathrm{for},0\le g,r\le L,2\le j\le n---\left(69\right)$

步骤4：该步骤确定在主要分组集合中最初的a个分组中b个被丢弃以及在第a个分组到达的时隙结束时缓存的占有率等级等于d的概率M(a，b，d)，其中1≤a≤n且0≤b≤a。当a＝1时概率M(a，b，d)可被表达为在前面等式62和63中定义的矢量S的函数。当a＞1时，概率M(a，b，d)可如以下所示的表达式使用A(k，g，j)和B(k，g，j)递归定义：

M(1，0，0)＝S₀q_Cp_D

M(1，0，1)＝S₀(q_Cq_D+p_Cp_D)+S₁q_Cp_D

M(1，0，d)＝S_d-2p_Cq_D+S_d-1(q_Cq_D+p_Cp_D)+S_dq_Cp_D，fof  2≤d≤L-2

$M(1,0,L-1)=S_{L-3}{p}_C{q}_D+S_{L-2}(q_C{q}_D+p_C{p}_D)+S_{L-1}(q_C{p}_D+\frac{1}{2}{p}_C{p}_D)$

$M(1,0,L)=S_{L-2}{p}_C{q}_D+S_{L-1}(q_C{q}_D+\frac{1}{2}{p}_C{q}_D)$

M(1，1，d)＝0，for 0≤d≤L-2

$M(\mathrm{1,1},L-1)=S_{L-1}\frac{1}{2}{p}_C{p}_D+S_L{p}_D$

$M(\mathrm{1,1},L)=S_{L-1}\frac{1}{2}{p}_C{q}_D+S_L{q}_D$

$M(a,0,d)=\underset{j=0}{\overset{L}{\Sigma }}M(a-\mathrm{1,0},j)·A(j,d,a),\mathrm{for},2\le a\le n$

$M(a,b,d)=\underset{j=0}{\overset{L}{\Sigma }}M(a-1,b,j)·A(j,d,a)+$

$\underset{j=0}{\overset{L}{\Sigma }}M(a-1,b-1,j)·B(j,d,a),\mathrm{for},2\le a\le n,1\le b\le a-1$

$M(a,a,d)=\underset{j=0}{\overset{L}{\Sigma }}M(a-1,a-1,j)·B(j,d,a),\mathrm{for},2\le a\le n$

步骤5：该步骤确定k个主要数据分组中v个被丢弃、最初的a个EC分组中b个被丢弃以及在第a个EC分组到达的时隙结束时缓存的占有率等于d的概率D(a，b，d，v)，其中1≤a≤n-k，0≤b≤a且0≤v≤k。当a＝1时概率D(a，b，d，v)可被表达为M(k，v，j)、A(j，d，k)和B(j，d，k)的函数。当a＞1时，概率D(a，b，d，v)可如下列表达式所示使用D(a-1，b，d，v)、A(j，d，k)和B(j，d，k)递归定义：

$D(\mathrm{1,0},d,v)=\underset{j=0}{\overset{L}{\Sigma }}M(k,v,j)·A(j,d,k+1)$

$D(\mathrm{1,1},d,v)=\underset{j=0}{\overset{L}{\Sigma }}M(k,v,j)·B(j,d,k+1)$

$D(a,0,d,v)=\underset{j=0}{\overset{L}{\Sigma }}D(a-1,0,j,v)·A(j,d,a+k),\mathrm{for}2\le a\le n-k$

$D(a,b,d,v)=\underset{j=0}{\overset{L}{\Sigma }}D(a-1,b,j,v)·A(j,d,a+k)+$

$\underset{j=0}{\overset{L}{\Sigma }}D(a-1,b-1,j,v)·B(j,d,a+k),\mathrm{for}2\le a\le n-k,1\le b\le a-1$

$D(a,a,d,v)=\underset{j=0}{\overset{L}{\Sigma }}D(a-1,a-1,j,v)·B(j,d,a+k),\mathrm{for}2\le a\le n-k$

k个主要数据分组中的v个被丢弃且(n-k)个EC分组中的b个被丢弃的概率H(v，b)可如下表达：

$H(v,b)=\underset{d=0}{\overset{L}{\Sigma }}D(n-k,b,d,v),\mathrm{for}0\le v\le k---\left(70\right)$

通过EC处理得以恢复的数据分组的数目的平均或期望值E_rec可被表达为：

$E_{\mathrm{rec}}=\underset{v=0}{\overset{k}{\Sigma }}\underset{b=0}{\overset{n-k}{\Sigma }}H(v,b)·J(v,b)---\left(71\right)$

其中$J(v,b)=\left(\begin{array}{cc}k,& v+b\le n-k\\ k-v,& \mathrm{otherwise}\end{array}\right).$

F.CBR-业务模型的近似算法

对于柏努利-业务模型来说积计算E_rec近似值的算法通常是不需要的，因为如等式48中所示的E_rec的精确计算要求计算等式42、当k＝L-1时的等式43和等式44，其可通过计算复杂度为O(1)来实现，以及需要应用等式46，等式46的应用的计算复杂度为O(nk)。计算E_rec算法的整个计算复杂度为O(nk)。这些复杂性指标假设所有需要的二项式系数均预先计算好并被保存以便随后使用。使用用C编程语言编写的且可由加利福尼亚Santa Clara的Intel公司提供的3.4GHz微处理器执行的实现，E_rec的计算需要小于1毫秒(msec)的时间。这已足够快以达到许多应用的实时要求。

不幸地是，对于CBR-业务模型来说计算E_ec近似值的算法是需要的，因为以上讨论的精确算法的计算复杂度非常高。

1.精确算法的复杂性

由以上讨论的5个步骤算法推导得出的等式71在此被称为精确算法，因为它被用于非近似地计算期望值E_rec。步骤1完成m·k个矩阵乘积，然后计算(L+1)×(L+1)矩阵的奇异值分解。这些操作的计算复杂度为O(mkL³)。完成步骤2和3所需要的操作的计算复杂度可以忽略不计。在步骤4中用于计算概率M(a，b，d)的操作的计算复杂度为O(k²L)。在步骤5中用于计算概率D(a，b，d，v)的操作的计算复杂度为O((n-k)²kL²)。5个步骤的算法的整个复杂性大概为((mkL³+k²L+((n-k)²kL²)。然而，在实际执行中，缓存L的大小可能比值n、k大一个或两个数量级；因此，该算法的整个复杂性大概为O(mkL³)。

表I中的记录显示了对于不同大小的缓存，使用用C编程语言编写且由3.4GHz Pentium微处理器的电脑执行的5步算法的示例实现来计算E_rec所需要的时间量。步骤1中的奇异值分解由在Press et al.，“Numerical Recipes inC++：The Art of Scientific Computing”，2nd ed.，Cambridge University Press，1992中描述的程序svdcmp得以完成。

表I

在典型的多媒体无线网络中，分组处理装置10可以通过许多商业上可获取的基于IEEE 802.11的无线接入点(AP)得以实现，这些无线接入点典型地有用于300或更多分组的缓存存储容量。表I中的记录显示对于这样一个AP通过以上提到的示例实现来计算期望值E_rec至少需要632毫秒。不幸的是，该计算必须在小于至少一个数量级的时间内完成，以允许多种多媒体应用的EC参数(n，k)的实时调整。以下将描述有较低复杂性的算法的推导，该算法可在少很多的时间内计算E_rec的近似值。

2.收缩-状态(Collapsed-State)模型

以上描述的5步算法的目的是确定EC参数(n，k)以使EC恢复后的信息损失最小化。只有当由于缓存溢出引起分组处理装置10将一个或多个分组丢弃而发生分组损失时，才需要计算该算法。当缓存占有率的等级为L或接近L，且竞争分组和主要分组在分组处理装置10处的累积到达速率高于该装置从缓存发送分组的速率时，将会发生缓存溢出。换句话说，对于非常接近于L的几乎几个k值，稳态矢量S的项S_k都为0或者接近于0。

数值试验证实了这些期望值(expectation)。在附图5至7中的曲线图显示了对于不同竞争业务速率p_C稳态概率S_k的分布。在这三个例子中，m＝4，n＝6，k＝5以及p_D＝0.8。当到达速率的和p_A+p_C等于p_D时(这当p_C＝0.5时发生)，该模型将达到一平衡状态。对于如图5所示的例子，p_C＝0.52，比平衡速率稍高。如该图所示，稳态概率S_k随着k的增加迅速提高，然而，只有当k＞95的值时，才能发现稳态概率大于0.01。即使增加p_C以使累积到达速率p_A+p_C大于传输速率p_D，例如分别由附图6和7所示的p_C＝0.6和p_C＝0.66，稳态概率S_k仍然为0或接近于0，除非k非常接近L。

可将这种现象(behavior)用于开发良好的近似算法。业务模型的任何具有0或接近于0的稳态概率S_k的状态对系统行为没有显著影响，因为系统基本上从不处于该状态。在如图5至7所示的例子中，所有S_k≈0的状态中的大多数对稳态系统的动态(dynamics)影响很小或没有影响。因此，在稳态矢量S的计算中可以将这些状态忽略，而不会对计算结果改变很大，且这些状态的忽略也不会对E_rec的计算值改变很大。

基于该观察结论，近似算法可被推导得出以仅为稳态k计算E_rec，其中S_k＞ε，ε是一个很小的阈值。该近似算法使用收缩状态矢量C，在该矢量中所有S_k＞ε的状态k都由单独的矢量项$C_k=S_{k+L_0}$表示，所有其他的S_k≤ε的状态k收缩到单个状态C₀。假设k≤L₀时S_k≤ε，其中L₀是缓存占有率的阈值。因此，收缩状态矢量C只有L-L₀+1个项C_k，其中，0≤k≤L-L₀。

通过用值L-L₀代替L重新定义等式3中所示的转移矩阵，有L+1个项的稳态矢量S可以由仅有L-L₀+1个项的收缩状态矢量C近似地表示。在状态C_a和C_b间的转换概率被定义为0≤a，0≤L-L₀。如果a，b＞0，该转移矩阵精确地描述了缓存占有率的动态性，但是如果a＝0或者b＝0，则它仅近似地描述了缓存占有率的动态性。如果阈值ε选择得足够小，由于收缩状态C₀被假设为仅以εL₀的概率非常频繁地发生，则该近似值不应当对C_k的计算的精确性有任何显著的影响，其中1≤k≤L-L₀。具体来说，希望当1≤k≤L-L₀时绝对差非常小。

收缩状态矢量C可通过将奇异值分解应有于等式62或63，然后通过如上所述使用将矢量π代替为矢量C的等式52将结果归一化(normalize)，而得以计算。计算矢量C后，通过使用矢量C而不是矢量S从等式71可以计算出E_rec的近似值。如图5至7所示的例子表明值L₀可被认为接近于值L，这将计算复杂度从O(mkL³)减小到O(mk(L-L₀)³)。通过将表I中的缓存大小L替代为L-L₀，可以看出当L₀非常接近L时，示例实现的执行时间可被减少一或多个数量级。L₀的值可以被选取以使近似算法的实现能满足多种多媒体应用的实时要求。

必须在近似算法可以使用之前确定值L₀。数值模拟表明只要p_A+p_C＞p_D+μ时，L₀可以选取为小到L₀＝10而不明显降低近似算法精确性，其中μ＝0.1。通过使用由等式71计算出来的E_rec的精确值来确定什么L₀值使近似算法能在可接受的精确度等级估计E_rec，可以预先计算好一组适合于不同μ值的值L₀以与近似算法一起使用。

该收缩状态近似值技术可被用于为基本上任何业务模型获取具有减低了计算复杂度的算法。

G.应用

以上描述的技术可被用于推导算法以在分组通信系统中完成各种应用。

一个应用在给定参数p_A、p_C、p_D、L和EC参数(n，k)的情况下，使用以上描述的算法计算EC恢复后主要数据分组的损失概率。

一个应用确定调整EC参数(n，k)以使EC恢复后主要数据分组的损失最小化。完成该应用的一种方法是首先确定对于考虑中的通信系统可行的所有参数值对(n，k)。一些影响系统的限制，如通信通道带宽和最大允许延时，也限制了EC参数(n，k)的选择。对带宽的限制施加了对比率的限制，对延时的限制施加了对参数n的限制。所有可行的参数值(n，k)的组可通过建立延时和带宽的最大可接受量，然后确定满足这些要求的所有EC参数对(n，k)，而得以确定。以上推导出来的算法可被应用于参数p_A、p_C、p_D、L和可行的EC参数值(n，k)的全部或子集以计算相关联的损失概率。获取最低损失概率的EC参数值(n，k)可被选取作为最佳参数组。

另一个应用为数据源2发送主要分组确定最佳速率。在该应用中，选取EC参数(n，k)的值，以上推导得出的算法被应有于不同的分组达到速率p_A以计算相关联的损失概率。在许多情况下，实际考虑限制了能被考虑的速率。实现最低损失概率的速率可被用于设置数据源的最佳发送速率。

可选地，推导出来的算法可被应用于EC参数(n，k)和分组达到速率的值的范围以确定实现最低损失概率的设置。

另外一个应用在给定参数p_A、p_D、L、EC参数(n，k)和EC恢复后丢失主要数据分组的速率的情况下计算竞争分组到达概率p_C。以上描述的应用假设参数p_A、p_C、p_D和L的值是已知的。如果p_C值是未知的，如果不提供EC保护，则p_C值可以通过参数p_A、p_D、P_loss和L获取，如果提供EC保护，则p_C值可以通过参数p_A、n、k、p_D、E_loss和L获取。例如，计算p_C的迭代处理可以在数据源2中完成。该处理可以从数据源2获取p_A、n和k的值，从接收机20获取p_D和P_loss或E_loss的值。L的值通常是先验(a priori)已知的，但如果在其它方式中不是已知的，可以从分组处理装置10获取。在以下章节描述可完成迭代的方法。通过该处理计算的p_C值可被用于其他应用，例如作为以上描述算法的输入参数。

如果不提供EC保护，柏努利-业务系统的p_C值可以通过由等式2和等式42至44所定义的关系得以确定。对于CBR-业务系统，该值可以通过由等式2定义的关系和上面关于等式53描述的技术得以确定。对于任何类型的系统，由这些等式定义的关系建立了p_C和P_loss间单调的一对一的映射。使用该映射属性，p_C可以通过收敛于(converge to)p_C值的迭代二分查找(binary-chop search)得以确定。

如果提供EC保护，柏努利-业务系统的p_C值可以通过由等式2和48定义的关系得以确定。对于CBR-业务系统，该值可以通过由等式2和71定义的关系得以确定。对于任何类型的系统，由这些等式定义的关系建立了p_C和E_rec间单调的一对一的映射。使用该映射属性，p_C可以通过收敛于p_C值的迭代二分查找得以确定。

在许多实现中，可行的n和k的选择受到带宽和延时要求的限制。在前述章节描述的算法可用于在所有可行的n和k的选择中查找EC参数(n，k)以使EC恢复后的损失概率最小化。p_C值如刚才描述那样得以确定，然后完成对所有可行的n和k值的查找以找到最佳值。

H.实现

如图1所示，通信通道3、5、11、21和22可以由基本上任何技术和媒体得以实现，所述媒体例如通过金属线的电信号、通过光纤的光信号和通过空间发射的无线电频率(RF)。本发明可被有利地应用于如图1显示的通信系统中，在该系统中通信通道11是无线RF通道，所有其他通信通道是电通道或光通道。

实施本发明各方面所需要的功能可由以各种方式实现的元件得以完成，包括离散逻辑元件、集成电路、一个或多个ASIC和/或程序控制的处理器。这些元件得以实现的方式对本发明来说是不重要的。

本发明的软件实现可通过各种机器可读介质得以承载，例如遍及包括从超声波到紫外线频率的频谱的基带或调制通信通道，或者存储介质，该存储介质使用包括磁带、卡或盘、光卡或光盘和在包括纸的介质上可检测的标记的、基本上任何记录技术来传达信息。