用於優化無線網絡中多媒體流的前向糾錯的方法和系統的製作方法

2023-07-22 13:29:36

專利名稱：用於優化無線網絡中多媒體流的前向糾錯的方法和系統的製作方法
技術領域：
本發明涉及優化用於處理布置在傳輸給接收機的分組中的信息流的裝置的操作，更具體地來說，涉及調整該裝置的操作以便在接收機使分組損失最小化。本發明可以被有利地用於在無線網絡中傳輸攜帶多媒體信息的分組流的系統。

背景技術：
在無線網絡中實時多媒體業務的遞送被期望是第三代蜂窩、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的概率由符號pA表示，其中0≤pA≤1。「CBR-業務模型」描述了一個通信系統，在該通信系統中主要分組以可由確定性過程描述的方式到達分組處理裝置10，在該確定性過程中分組以每m個時隙一次的固定速率到達。為了便於討論，比例

也被稱為到達概率並用符號pA表示。由於假設分組攜帶固定量的信息或固定數目的比特，固定分組到達率等於固定比特率(CBR)；因此第二模型被稱為CRB-業務模型。
兩個模型都假設由除數據源2外的其他數據源提供的所有競爭分組都以能被具有柏努利概率分布的概率過程描述的方式到達分組處理裝置10。競爭分組在給定時隙內到達分組處理裝置10的概率由符號pC表示，其中0≤pC≤1。該假設對大多數應用都是合理的，因為由其他數據源用於發送競爭分組的處理一般是未知的。可採用任何能用於測量或估計競爭分組到達的技術來推導得出競爭分組到達過程的分布，以下描述的技術可用於構造一個反映到達過程的模型。然而，如果到達過程是未知的，柏努利分布是一個適當的假設。由於以下描述的模型僅對所有競爭分組的累積到達概率pC感興趣，因此這些模型假設僅有一個用於競爭業務的數據源存在。這一個源可以代表多個數據源的累積影響。
兩個模型還假設，對於在其中至少一個分組被保存到緩存中的每一時隙，分組處理裝置10成功地從緩存中檢取一個分組並把該分組以由符號pD表示的概率通過通信通道11進行發送，其中0≤pD≤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的概率pD。如果需要，通過定義由接收機20接收的部分被破壞的分組的附加概率，損壞分組能被至少部分恢復的概率可被結合到該模型中。採用通信通道11的吉爾伯特模型(Gilbert model)可以從該附加概率推導得出一個適當的概率pD(參見Bolot et al.，」Adaptive FEC-based error control for Internettelephony」，IEEE Infocom 2003，San Francisco.)。
在有多個競爭數據源的系統中，可能在一個時隙中平均多於一個競爭分組能到達，這可以用關係pC＞1來表達。為了簡化計算，以下模型假設0≤pC，pA，pD≤1。通過減小每一時隙的長度以使pC，pA，pD＜1，能實現該假設。
以下描述的模型和隨後的導出考慮了分組損失，而沒有考慮延遲和延遲抖動。並且，模型考慮了僅從數據源流向接收機的分組業務，而沒有考慮從接收機流向數據源的信號。
2.緩存操作的分析 以下描述的模型假設分組處理裝置10具有長度為L的隊列或緩存，並且在每一時隙，該裝置嘗試在該緩存中保存從數據源2接收到的任何主要分組和從其他數據源接收到的任何競爭分組。根據這些模型，由該裝置完成的將分組保存到緩存中的操作可被描述如下 1.在任何給定時隙，該裝置以概率pA從數據源2接收主要分組和以概率pC從其他源接收競爭分組。如果在相同時隙接收到主要分組和競爭分組，假設兩個分組中的其中任何一個比另一個先到達的概率是相同的。換句話說，假設競爭分組比主要分組先到的概率等於0.5。
2.在給定時隙中能到達的主要分組和競爭分組的總數j可以是在組{0，1，2}中的任何數。根據以下規則，到達的分組可能被保存在緩存中或可能被丟棄 a)如果緩存佔有率的等級恰在這些分組的到達之前小於或等於L-j，則所有到達的分組都被保存到緩存中。
b)如果j＝2且緩存佔有率的等級為L-1，則兩個到達分組中較早的那個被保存在緩存中，而較晚到達的分組被丟棄。
c)否則，所有到達的分組都被丟棄。
3.在任何給定時隙，分組處理裝置10以概率pD從緩存中檢取分組，並將分組沿通信通道11發送，以使該分組攜帶的信息能無損壞的被接收。分組以FIFO的順序被存入緩存和從緩存檢取。如果緩存是空的，不檢取和發送分組。如果一個分組被檢取並被發送，則緩存佔有率的等級減1。
以下描述的模型包括一穩態矢量，它描述緩存的統計佔有率。該矢量被表達為 P＝(PN)，其中0≤N≤L(1) 其中PN＝在時隙結束時在緩存中保存N個分組的概率；且 L＝緩存的大小或長度。
該穩態矢量可以表達為參數pA、pC、pD和L的函數。以下將導出該函數的表達式。
C.分組損失概率 1.介紹 如果在主要分組到達分組處理裝置10的時隙期間，存在兩種情況中的一種，來自數據源2的主要分組將被分組處理裝置10丟棄(1)緩存佔有率為L或者(2)緩存佔有率為L-1且競爭分組比主要分組先到達。在給定時隙中到達的主要數據分組將被丟棄的概率Ploss可被表達為 係數二分之一反映了當主要分組和競爭分組在相同時隙到達時，競爭分組比主要分組先到達的概率等於0.5的假設。
穩態矢量P可以從轉移矩陣(transition matrix)計算得到，該轉移矩陣的項(entry)代表了在P的不同狀態間轉換的概率。轉移矩陣的通用參數表達式被首先開發。然後通過對參數做適當的選擇就能將該通用表達式適用於柏努利-業務和CBR-業務模型。
2.轉移矩陣 轉移矩陣用符號T表示，符號Ta，b被用於表示緩存佔有率等級在連續時隙間從a變化到b的概率，其中0≤a，b≤L。在從緩存中移出(remove)任何所發送的分組後的每一時隙結束時測量緩存佔有率的等級。符號(Ta，b)u被用於表示緩存佔有率的等級經過u個時隙從a變化到b的概率，其中u≥1；因此Ta，b＝(Ta，b)1。
可以如下表達轉移矩陣中的元素
其中qA＝在時隙中沒有主要分組到達的概率，或者qA＝1-pA； qC＝在時隙中沒有競爭分組到達的概率，或者qC＝1-pC； qD＝在時隙中未成功發送數據分組的概率，或者qD＝1-pD。
在嘗試發送失敗、沒有嘗試發送和作為服務質量保護處理的一部分重傳分組的那些時隙中數據分組未成功發送。
例如，項T0，0代表了假設在一時隙結束時緩存是空的，在下一時隙結束時該緩存仍然是空的的概率。這種情況可以由三種可能的情況引起，這三種可能的情況的概率由在表達式3中所示的T0，0的三個項中的每一個所表達。第一項qAqC表示在下一時隙中沒有主要分組和競爭分組到達的概率。第二項qApCpD表示沒有主要分組達到、競爭分組到達並被保存在緩存中和從緩存中取出分組並發送的概率。第三項pAqCpD表示主要分組到達並被保存在緩存中、沒有競爭分組到達和從緩存中移除分組並發送的概率。
D.柏努利-業務II類分組損失的概率 用於計算無EC保護的柏努利分布業務II類分組損失概率的模型被首先開發。該模型然後被修改以計算有EC保護的柏努利分布業務分組損失的概率。
1.無EC保護的柏努利-分布業務的穩態模型 開發柏努利-業務模型的第一步是推導無EC保護的柏努利-分布業務模型的穩態矢量P的計算。在許多馬爾可夫模型的應用中，為穩態矢量P推導得出精確的公式是不可能的，但該矢量可以表達為矩陣分解的奇異值分解的結果。不幸的是，該方法並沒有吸引力，因為它的解決方案不是封閉形式的並且計算非常複雜。然而，線性迭代公式理論被用於為P建立封閉形式的表達式。通過首先在定理1為P推導得出一個相當複雜和計算花費大的公式，該公式將在定理2中被簡化。
定理1的證明如下。
定理1 其中 W＝pApC+qApCqD+pAqCqD(8) X＝pApCqD(9) Y＝qAqCpD(10) 通過歸納法證明定理1。從式3給出的轉移矩陣定義，可以推導出以下關係 P0＝P0(qAqC+qApCpD+pAqcpD)+P1qAqCpD (12) P1＝P1(qAqCqD+qApCpD+pAqcpD)+P0(pApCpD+pAqcqD+qApCqD)+P2qAqCpD(13) Pj＝Pj(qAqCqD+qApCpD+pAqcpD)+Pj-1(pApCpD+pAqcqD+qApCqD)+ Pj+1qAqCpD+Pj-2pApCqD，2≤j≤L-2 (14) PL-1＝PL-1(qAqCqD+qApCpD+pAqcpD+pApCpD)+ PLpD+PL-2(pApCpD+pAqcqD+qApCqD)+PL-3pApCqD (15) PL＝PLqD+PL-1(pAqCqD+qApCqD+pApCqD)+PL-2pApCqD(16) 使用由表達式7至11給出的定義，在表達式12至15中給出的關係可表示為 P1Y＝P0W (17) P2Y＝P1(W+Y)-P0(W-X) (18) Pj+3Y＝Pj+2(W+Y)-Pj+1(W-X)-PjX，0≤j≤L-4 (19) PLpD＝PL-1(1+Y-pD-qAqCqD)-PL-2(W-X)-PL-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 它等價於 W3Bj+3＝W3Bj+2+W2YBj+2-W2YBj+1+WXYBj+1-XY2Bj (22) 其可被重新安排為 W3Bj+3-W3Bj+2-WXYBj+1＝W2YBj+2-W2YBj+1-XY2Bj (23) 已知 其中

表示等於可從i種可能性中選取無順序的j個結果的方法數的二項式係數。
使用等式7中的表達式，等式23左手側的項能被改寫為以下形式 通過將該關係應用於等式24和25中，並且合併和簡化這些項，等式23左手側如下所示等於零 等式23右手側的項可被表示為如下形式 通過將該關係應用於等式24和25，並且合併和簡化這些項，等式23右手側如下所示等於零 根據等式23、29和33可以得出對於j+3等式5為真(true)。對於j＝L，根據等式5和20可以得出等式6。根據等式5和6及可以得出等式4。
為定理1中的Bj推導得出的表達式可以通過定義B0＝1如在等式7中所示的那樣擴展Bj的定義得以簡化。實現如下所示 引理1 等式34中的關係等價於 從等式25可以看出在等式35左手側的第一項與該等式右手側的第一項都等於1。從等式24可以看出等式35左手側的第二項等於該等式右手側的第二項和第三項的和，如等式36所示 根據檢驗(inspection)，可以看出，如果求和項不在l＝1到1/2j的求和範圍內，等式35左手側的第三項和該等式35右手側的第四項都等於0；如果該求和項在該求和範圍內，則都等於1。這建立了引理1，引理1顯示了項Bj可以被表達為廣義Fibonacci數。
引理2 級數被定義為 x0＝x1＝1且xi＝KAxi-1+KBxi-2，對於i≥2 (37) 其中KA和KB是正實數。
如果將α和β定義為等式x2＝KAx+KB的根，或者 且其被限制為互不相等，則根據線性迭代方程式的理論可知 根據表達式37和38的檢驗可以看出對於i＝0，1等式38為真，通過歸納可以看出對於i≥2等式38為真。通過將如等式37所示的關係應用到等式34的Bj的表達式中，可得出KA和KB有如下值 KA＝1 可得出 其中 這意味著β＝1-α。通過使用該關係代替等式38中的β，在等式7中所示的Bj的表達式可以被改寫為 該式比等式7中的表達式計算複雜度小。
使用在等式39和40中的關係代替Bj和KC，使等式4中的項可被改寫為 通過將等式4、5和6改寫為如下形式可以獲得比在定理1中推導得出的算法計算複雜度小的、計算穩態矢量P的算法 其中 W＝pApC+qApCqD+pAqCqD X＝pApCqD Y＝qAqCpD 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分組的概率相乘計算得到 其中pi(k，n)＝丟失i個數據分組和至少s個EC分組的概率；和 s＝max(0，n-k-i+1). 在等式46中示出的概率Ploss使用在等式45中示出的修改的pA值，如在等式2中所示那樣得以計算。Ploss現在表示主要數據分組或主要EC分組將被丟棄的概率。
無EC恢復地丟失主要數據分組的概率Eloss等於 EC恢復後的恢復主要數據分組的概率Erec等於 Erec＝1-Eloss(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) 該到達方案形式上可描述為 其中ei＝ti-ti-1，2≤i≤n；和 ti＝一組主要分組中的第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-業務模型被調整。對於柏努利-分布業務，對於所有時隙到達過程是統計相等的，因為該處理僅取決於到達概率pA。因此，上述的轉移矩陣T能很好的描述任何兩個相繼時隙間的概率轉換。對於CBR業務，平均或複合到達概率為然而，對於CBR業務的到達過程是確定性的，每一時隙可被放置到兩類中的一類。當時隙i＝1(mod m)時，主要分組到達，且對於這些時隙的轉移矩陣F可以通過將表達式3中的pA用值1代替、qA用值0代替來獲取。當時隙i≠1(modm)時，沒有主要分組達到，且對於這些時隙的轉移矩陣G可以通過將表達式3中的pA用值0代替、qA用值1代替來獲取。轉移矩陣F和G的乘積(product)指定了一系列時隙中分組的到達。有分組到達的每一時隙被F矩陣代表，沒有分組到達的每一時隙被G矩陣代表。
3.無EC保護的CBR-業務模型的分組損失概率 在無EC保護的CBR-業務模型中的緩存佔有率的穩態矢量π可被表達為以下形式 π＝(FGm-1)Tπ (51) 其中T代表了矩陣乘積的轉置(transposition)。
等式51可通過矩陣(FGm-1)T-I的奇異值分解得以求解，其中I時所有對角項都為1的對角矩陣，從而獲取一維的解空間，並使用等式 來為π確定最終值。使用穩態矢量π而不是使用穩態矢量P，主要數據分組的損失概率可以由類似等式2的方程計算得出 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) 值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意味著 如等式61所示的表達式不可能為真，因為左手側是整數而右側不可能是整數。這與在等式59中表達的假設矛盾，這意味著w與m-1(mod m)不同餘。
通過以上描述的到達過程的定義，穩態矢量S可被表達為 S＝(Fw-m+1(Gz-1F)f(Gm-1F)yFm-1)TSfor m-1＜w(62) S＝(F(Gm-1F)yFwGz-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)可被表達為 對於0≤g，h≤L(64) 其中xj為正整數，且 條件概率的定義表達了如下事實在m-1個中間時隙之間有一些在其中主要分組到達的時隙，由F矩陣表示，還有一些在其中沒有主要分組到達的時隙，由G矩陣表示。特別地，假設在當第(j-1)個數據分組到達時的時隙結束時緩存佔有率為g的情況下，在第j個主要分組到達前的時隙結束時緩存佔有率為h的條件概率R(ej-1，g，h)在2≤j≤n時得以計算。

其中(Fx)g，h＝矩陣F升到第x次冪的第g行第h列的項； (Gy)g，h＝矩陣G升到第y次冪的第g行第h列的項； (FxGy)g，h＝矩陣乘積FxGy的第g行第h列的項；且 由於項R(ej-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是在主要分組到達的時隙結束時的緩存佔有率，如果兩種情況中的任一中為真，則到達的分組不會被丟棄沒有競爭分組到達且以概率qCpD從緩存中發送分組，或競爭分組到達但它是在主要分組之後到達的，且以概率

從緩存中發送分組。
●如果h＝L-1且r＝L，其中r是在主要分組到達的時隙結束時的緩存佔有率，如果兩種情況中的任一中為真，則到達的分組不會被丟棄沒有競爭分組到達且沒有以概率qCqD從緩存中發送分組，或競爭分組到達但它是在主要分組之後到達的，且沒有以概率

從緩存中發送分組。
●如果h＝L，達到的主要分組被丟棄。
假設在當前時隙中主要分組到達，並且假設在上一時隙結束時緩存的佔有率為h，在當前時隙結束時緩存佔有率等於r且到達的主要分組不會被丟棄的條件概率可表達為
類似地，假設在當前時隙中主要分組到達，並且假設在上一時隙結束時緩存的佔有率為h，在當前時隙結束時緩存佔有率等於r且到達的主要分組被丟棄的條件概率可表達為
步驟3該步驟確定假設在分組集合中的第(j-1)個主要分組到達的時隙結束時緩存的佔有率為g的情況下，主要分組集合中第j個分組到達的時隙結束時緩存的佔有率為r且第j個主要分組不被丟棄的條件概率。該條件概率可被表達為 類似地，假設在分組集合中的第(j-1)個主要分組到達的時隙結束時緩存的佔有率為g的情況下，主要分組組中第j個分組到達的時隙結束時緩存的佔有率為r且第j個主要分組被丟棄的條件概率可被表達為 步驟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)＝S0qCpD M(1，0，1)＝S0(qCqD+pCpD)+S1qCpD M(1，0，d)＝Sd-2pCqD+Sd-1(qCqD+pCpD)+SdqCpD，fof 2≤d≤L-2 M(1，1，d)＝0，for 0≤d≤L-2 步驟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)遞歸定義 k個主要數據分組中的v個被丟棄且(n-k)個EC分組中的b個被丟棄的概率H(v，b)可如下表達 通過EC處理得以恢復的數據分組的數目的平均或期望值Erec可被表達為 其中 F.CBR-業務模型的近似算法 對於柏努利-業務模型來說積計算Erec近似值的算法通常是不需要的，因為如等式48中所示的Erec的精確計算要求計算等式42、當k＝L-1時的等式43和等式44，其可通過計算複雜度為O(1)來實現，以及需要應用等式46，等式46的應用的計算複雜度為O(nk)。計算Erec算法的整個計算複雜度為O(nk)。這些複雜性指標假設所有需要的二項式係數均預先計算好並被保存以便隨後使用。使用用C程式語言編寫的且可由加利福尼亞Santa Clara的Intel公司提供的3.4GHz

微處理器執行的實現，Erec的計算需要小於1毫秒(msec)的時間。這已足夠快以達到許多應用的實時要求。
不幸地是，對於CBR-業務模型來說計算Eec近似值的算法是需要的，因為以上討論的精確算法的計算複雜度非常高。
1.精確算法的複雜性 由以上討論的5個步驟算法推導得出的等式71在此被稱為精確算法，因為它被用於非近似地計算期望值Erec。步驟1完成m·k個矩陣乘積，然後計算(L+1)×(L+1)矩陣的奇異值分解。這些操作的計算複雜度為O(mkL3)。完成步驟2和3所需要的操作的計算複雜度可以忽略不計。在步驟4中用於計算概率M(a，b，d)的操作的計算複雜度為O(k2L)。在步驟5中用於計算概率D(a，b，d，v)的操作的計算複雜度為O((n-k)2kL2)。5個步驟的算法的整個複雜性大概為((mkL3+k2L+((n-k)2kL2)。然而，在實際執行中，緩存L的大小可能比值n、k大一個或兩個數量級；因此，該算法的整個複雜性大概為O(mkL3)。
表I中的記錄顯示了對於不同大小的緩存，使用用C程式語言編寫且由3.4GHz Pentium微處理器的電腦執行的5步算法的示例實現來計算Erec所需要的時間量。步驟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通過以上提到的示例實現來計算期望值Erec至少需要632毫秒。不幸的是，該計算必須在小於至少一個數量級的時間內完成，以允許多種多媒體應用的EC參數(n，k)的實時調整。以下將描述有較低複雜性的算法的推導，該算法可在少很多的時間內計算Erec的近似值。
2.收縮-狀態(Collapsed-State)模型 以上描述的5步算法的目的是確定EC參數(n，k)以使EC恢復後的信息損失最小化。只有當由於緩存溢出引起分組處理裝置10將一個或多個分組丟棄而發生分組損失時，才需要計算該算法。當緩存佔有率的等級為L或接近L，且競爭分組和主要分組在分組處理裝置10處的累積到達速率高於該裝置從緩存發送分組的速率時，將會發生緩存溢出。換句話說，對於非常接近於L的幾乎幾個k值，穩態矢量S的項Sk都為0或者接近於0。
數值試驗證實了這些期望值(expectation)。在附圖5至7中的曲線圖顯示了對於不同競爭業務速率pC穩態概率Sk的分布。在這三個例子中，m＝4，n＝6，k＝5以及pD＝0.8。當到達速率的和pA+pC等於pD時(這當pC＝0.5時發生)，該模型將達到一平衡狀態。對於如圖5所示的例子，pC＝0.52，比平衡速率稍高。如該圖所示，穩態概率Sk隨著k的增加迅速提高，然而，只有當k＞95的值時，才能發現穩態概率大於0.01。即使增加pC以使累積到達速率pA+pC大於傳輸速率pD，例如分別由附圖6和7所示的pC＝0.6和pC＝0.66，穩態概率Sk仍然為0或接近於0，除非k非常接近L。
可將這種現象(behavior)用於開發良好的近似算法。業務模型的任何具有0或接近於0的穩態概率Sk的狀態對系統行為沒有顯著影響，因為系統基本上從不處於該狀態。在如圖5至7所示的例子中，所有Sk≈0的狀態中的大多數對穩態系統的動態(dynamics)影響很小或沒有影響。因此，在穩態矢量S的計算中可以將這些狀態忽略，而不會對計算結果改變很大，且這些狀態的忽略也不會對Erec的計算值改變很大。
基於該觀察結論，近似算法可被推導得出以僅為穩態k計算Erec，其中Sk＞ε，ε是一個很小的閾值。該近似算法使用收縮狀態矢量C，在該矢量中所有Sk＞ε的狀態k都由單獨的矢量項表示，所有其他的Sk≤ε的狀態k收縮到單個狀態C0。假設k≤L0時Sk≤ε，其中L0是緩存佔有率的閾值。因此，收縮狀態矢量C只有L-L0+1個項Ck，其中，0≤k≤L-L0。
通過用值L-L0代替L重新定義等式3中所示的轉移矩陣，有L+1個項的穩態矢量S可以由僅有L-L0+1個項的收縮狀態矢量C近似地表示。在狀態Ca和Cb間的轉換概率被定義為

0≤a，0≤L-L0。如果a，b＞0，該轉移矩陣精確地描述了緩存佔有率的動態性，但是如果a＝0或者b＝0，則它僅近似地描述了緩存佔有率的動態性。如果閾值ε選擇得足夠小，由於收縮狀態C0被假設為僅以εL0的概率非常頻繁地發生，則該近似值不應當對Ck的計算的精確性有任何顯著的影響，其中1≤k≤L-L0。具體來說，希望當1≤k≤L-L0時絕對差

非常小。
收縮狀態矢量C可通過將奇異值分解應有於等式62或63，然後通過如上所述使用將矢量π代替為矢量C的等式52將結果歸一化(normalize)，而得以計算。計算矢量C後，通過使用矢量C而不是矢量S從等式71可以計算出Erec的近似值。如圖5至7所示的例子表明值L0可被認為接近於值L，這將計算複雜度從O(mkL3)減小到O(mk(L-L0)3)。通過將表I中的緩存大小L替代為L-L0，可以看出當L0非常接近L時，示例實現的執行時間可被減少一或多個數量級。L0的值可以被選取以使近似算法的實現能滿足多種多媒體應用的實時要求。
必須在近似算法可以使用之前確定值L0。數值模擬表明只要pA+pC＞pD+μ時，L0可以選取為小到L0＝10而不明顯降低近似算法精確性，其中μ＝0.1。通過使用由等式71計算出來的Erec的精確值來確定什麼L0值使近似算法能在可接受的精確度等級估計Erec，可以預先計算好一組適合於不同μ值的值L0以與近似算法一起使用。
該收縮狀態近似值技術可被用於為基本上任何業務模型獲取具有減低了計算複雜度的算法。
G.應用 以上描述的技術可被用於推導算法以在分組通信系統中完成各種應用。
一個應用在給定參數pA、pC、pD、L和EC參數(n，k)的情況下，使用以上描述的算法計算EC恢復後主要數據分組的損失概率。
一個應用確定調整EC參數(n，k)以使EC恢復後主要數據分組的損失最小化。完成該應用的一種方法是首先確定對於考慮中的通信系統可行的所有參數值對(n，k)。一些影響系統的限制，如通信通道帶寬和最大允許延時，也限制了EC參數(n，k)的選擇。對帶寬的限制施加了對比率

的限制，對延時的限制施加了對參數n的限制。所有可行的參數值(n，k)的組可通過建立延時和帶寬的最大可接受量，然後確定滿足這些要求的所有EC參數對(n，k)，而得以確定。以上推導出來的算法可被應用於參數pA、pC、pD、L和可行的EC參數值(n，k)的全部或子集以計算相關聯的損失概率。獲取最低損失概率的EC參數值(n，k)可被選取作為最佳參數組。
另一個應用為數據源2發送主要分組確定最佳速率。在該應用中，選取EC參數(n，k)的值，以上推導得出的算法被應有於不同的分組達到速率pA以計算相關聯的損失概率。在許多情況下，實際考慮限制了能被考慮的速率。實現最低損失概率的速率可被用於設置數據源的最佳發送速率。
可選地，推導出來的算法可被應用於EC參數(n，k)和分組達到速率的值的範圍以確定實現最低損失概率的設置。
另外一個應用在給定參數pA、pD、L、EC參數(n，k)和EC恢復後丟失主要數據分組的速率的情況下計算競爭分組到達概率pC。以上描述的應用假設參數pA、pC、pD和L的值是已知的。如果pC值是未知的，如果不提供EC保護，則pC值可以通過參數pA、pD、Ploss和L獲取，如果提供EC保護，則pC值可以通過參數pA、n、k、pD、Eloss和L獲取。例如，計算pC的迭代處理可以在數據源2中完成。該處理可以從數據源2獲取pA、n和k的值，從接收機20獲取pD和Ploss或Eloss的值。L的值通常是先驗(a priori)已知的，但如果在其它方式中不是已知的，可以從分組處理裝置10獲取。在以下章節描述可完成迭代的方法。通過該處理計算的pC值可被用於其他應用，例如作為以上描述算法的輸入參數。
如果不提供EC保護，柏努利-業務系統的pC值可以通過由等式2和等式42至44所定義的關係得以確定。對於CBR-業務系統，該值可以通過由等式2定義的關係和上面關於等式53描述的技術得以確定。對於任何類型的系統，由這些等式定義的關係建立了pC和Ploss間單調的一對一的映射。使用該映射屬性，pC可以通過收斂於(converge to)pC值的迭代二分查找(binary-chop search)得以確定。
如果提供EC保護，柏努利-業務系統的pC值可以通過由等式2和48定義的關係得以確定。對於CBR-業務系統，該值可以通過由等式2和71定義的關係得以確定。對於任何類型的系統，由這些等式定義的關係建立了pC和Erec間單調的一對一的映射。使用該映射屬性，pC可以通過收斂於pC值的迭代二分查找得以確定。
在許多實現中，可行的n和k的選擇受到帶寬和延時要求的限制。在前述章節描述的算法可用於在所有可行的n和k的選擇中查找EC參數(n，k)以使EC恢復後的損失概率最小化。pC值如剛才描述那樣得以確定，然後完成對所有可行的n和k值的查找以找到最佳值。
H.實現 如圖1所示，通信通道3、5、11、21和22可以由基本上任何技術和媒體得以實現，所述媒體例如通過金屬線的電信號、通過光纖的光信號和通過空間發射的無線電頻率(RF)。本發明可被有利地應用於如圖1顯示的通信系統中，在該系統中通信通道11是無線RF通道，所有其他通信通道是電通道或光通道。
實施本發明各方面所需要的功能可由以各種方式實現的元件得以完成，包括離散邏輯元件、集成電路、一個或多個ASIC和/或程序控制的處理器。這些元件得以實現的方式對本發明來說是不重要的。
本發明的軟體實現可通過各種機器可讀介質得以承載，例如遍及包括從超聲波到紫外線頻率的頻譜的基帶或調製通信通道，或者存儲介質，該存儲介質使用包括磁帶、卡或盤、光卡或光碟和在包括紙的介質上可檢測的標記的、基本上任何記錄技術來傳達信息。
權利要求
1、一種在通信系統中控制分組提供的方法，所述通信系統包括
第一數據源，其提供攜帶被布置在一組分組中的信息的源信號，
分組處理裝置，其接收源信號，將該組分組中的至少一些分組的信息保存在具有緩存大小的緩存中，以及發送包括如下信息的分組的輸出信號，即，所述信息中的至少一些信息被保存在緩存中，其中在該組分組中的至少一些分組的信息由於緩存已滿所引起的損失而從輸出信號中被遺漏，和
接收器，其接收輸出信號中的至少一些分組，
其中該方法包括
(a)接收一個或多個攜帶參數的信號，所述參數表示
緩存大小，
來自任何競爭數據源的競爭分組在時間間隔內被分組處理裝置接收到的幹擾概率，和
當緩存非空時分組處理裝置在時間間隔內成功發送分組的發送概率；
(b)從所述參數得出損失概率的一個或多個測量度，每一測量度代表數據分組中的信息丟失的概率，其中通過用於評估由緩存已滿引起的損失的處理得出損失概率的每一測量度，以及其中，有以下任一情形
(1)該處理具有獨立於緩存大小的計算複雜度，以及對於到達概率、發送概率和幹擾概率的所有值都從0到1的情況，損失概率的值從0到1，或
(2)該處理表示如下模型的解，在該模型中，在源信號中的分組根據確定性過程到達分組處理裝置；以及
(c)調整第一數據源的操作以減少數據分組中的信息由於分組處理裝置中的緩存已滿而丟失的似然性，其中，有以下任一情形
該組分組包括第一數目的數據分組和第二數目的糾錯分組，
接收機對所接收的分組應用糾錯處理以恢復被損壞或丟失的信息，
所述參數還表示第一數目和第二數目、以及在時間間隔內由分組處理裝置接收來自第一數據源的分組的到達概率，
根據所述參數得出損失概率測量度，該損失概率測量度表示在數據分組中的信息被丟失且未被糾錯處理恢復的概率，以及
響應於損失概率測量度來調整第一數據源的操作以改變第一數目或第二數目；
或者
根據所述參數得出對於多個到達概率中的每一個到達概率的相應損失概率測量度，其中每一到達概率表示在時間間隔內由分組處理裝置接收來自第一數據源的分組的概率，和
通過選擇如下到達概率以及改變第一數據源的操作以使得分組處理裝置以更接近地反映所選擇的到達概率的方式接收分組來調整第一數據源的操作，其中根據所述到達概率得出多個損失概率中的最小損失概率。
2、如權利要求1所述的方法，其中該處理表示如下模型的解，在該模型中，源信號中的分組根據確定性過程到達處理裝置，以及分組以固定速率到達，其中到達概率與固定速率成比例。
3、如權利要求1所述的方法，其中
到達概率遵循根據確定性過程到達處理裝置的在源信號中的分組的第一概率分布，和
幹擾概率遵循根據概率過程到達處理裝置的競爭分組的第二概率分布。
4、如權利要求1所述的方法，其中
到達概率遵循根據柏努利過程到達處理裝置的在源信號中的分組的第一概率分布，和
該處理在不需要近似的情況下得出損失概率的測量度，並具有與第二數目和第三數目的乘積成比例的計算複雜度，其中第三數目等於第一數目和第二數目的和。
5、如權利要求1到4任一權利要求所述的方法，其中該處理通過排除那些具有閾值以下的穩態概率的緩存佔有率狀態，通過近似得出損失概率的測量度。
6、如權利要求5所述的方法，其中該處理具有與第四數目的三次冪、第一數目和第五數目的乘積成比例的計算複雜度，其中第四數目表示那些具有高於閾值的穩態概率的緩存佔有率狀態的計數，第五數目與到達概率成反比。
7、如權利要求1到6的任一權利要求所述的方法，該方法通過將第二處理應用於代表緩存大小、第一和第二數目、到達概率、發送概率和初始損失概率的信息，而得出幹擾概率。
8、如權利要求7所述的方法，其中第二處理通過排除那些具有低於閾值的穩態概率的緩存佔有率狀態，通過近似得出幹擾概率的測量度。
9、一種通信系統，包括
第一數據源，其提供攜帶被布置在一組分組中的信息的源信號，
分組處理裝置，其接收源信號，將該組分組中的至少一些分組的信息保存在具有緩存大小的緩存中，以及發送包括如下信息的分組的輸出信號，即，所述信息中的至少一些信息被保存在緩存中，其中在該組分組中的至少一些分組的信息由於緩存已滿所引起的損失而從輸出信號中被遺漏，和
接收器，其接收在輸出信號中的至少一些分組，
其中第一數據源、分組處理裝置和接收機中的一個或多個具有被配置成執行如權利要求1至8中任一權利要求所述的方法的電路。
10、如權利要求9所述的通信系統，其中
該組分組包括第一數目的數據分組和第二數目的糾錯分組；和
接收機對所接收的分組應用糾錯處理以恢復被損壞或丟失的信息。
11、一種攜帶指令程序的介質，所述程序可由裝置執行的以執行如權利要求1至8中任一權利要求所述的用於在通信系統中控制分組提供的方法，其中該通信系統包括
第一數據源，其提供攜帶被布置在一組分組中的信息的源信號，
分組處理裝置，其接收源信號，將該組分組中的至少一些分組的信息保存在具有緩存大小的緩存中，以及發送包括如下信息的分組的輸出信號，即，所述信息中的至少一些信息被保存在緩存中，其中在該組分組中的至少一些分組的信息由於緩存已滿所引起的損失而從輸出信號中被遺漏，和
接收器，其接收在輸出信號中的至少一些分組。
12、如權利要求11所述的介質，其中
該組分組包括第一數目的數據分組和第二數目的糾錯分組；和
接收機對所接收的分組應用糾錯處理以恢復被損壞或丟失的信息。
全文摘要
通過響應於所計算的分組損失概率來調整一組糾錯(EC)參數，可以以優選的方式使得通信系統中的分組損失最小化。從應用於一組通信參數的、所得出的算法中得到計算的概率。根據通信系統的柏努利分布業務模型和固定比特率(CBR)業務模型得出算法。收縮-狀態模型被用於得出一種用於計算分組損失的近似概率的有效算法。還公開了算法的可選應用。
文檔編號H03M13/00GK101273570SQ200680023476
公開日2008年9月24日 申請日期2006年5月26日 優先權日2005年6月30日
發明者C·鮑爾, 蔣文宇 申請人:杜比實驗室特許公司