無線局域網(wǎng)內(nèi)組播場景中最小丟包重傳方法

(19)中華人民共和國國家知識(shí)產(chǎn)權(quán)局(12)發(fā)明專利說明書(10)申請(qǐng)公布號(hào)CN104219032A

(43)申請(qǐng)公布日2014.12.17(21)申請(qǐng)?zhí)朇N201410407682.8(22)申請(qǐng)日2014.08.19(71)申請(qǐng)人北京郵電大學(xué)地址100876北京市海淀區(qū)西土城路10號(hào)(72)發(fā)明人謝剛楊亞霖高錦春劉元安胡碧波劉凱明劉芳袁東明(74)專利代理機(jī)構(gòu)北京同恒源知識(shí)產(chǎn)權(quán)代理有限公司代理人張水俤(51)Int.CI H04L1/18權(quán)利要求說明書說明書幅圖(54)發(fā)明名稱 無線局域網(wǎng)內(nèi)組播場景中最小丟包重傳方法(57)摘要 本發(fā)明公開了一種無線局域網(wǎng)內(nèi)組播場景中最小丟包重傳方法，主要用于解決具有反饋鏈路的組播場景中的丟包恢復(fù)問題。該方法特征為：在多個(gè)用戶同時(shí)向一個(gè)AP請(qǐng)求相同數(shù)據(jù)傳輸服務(wù)的組播場景中，AP在接收到所有用戶反饋的丟包信息后，先根據(jù)本發(fā)明中的編碼方法生成一個(gè)編碼矩陣，然后再將編碼矩陣與原始數(shù)據(jù)包進(jìn)行比特按位異或形成組合重傳包，用戶在收到組合重傳包后根據(jù)本發(fā)明中的解碼方法進(jìn)行相應(yīng)地異或解碼恢復(fù)出丟包。該方法可以將多播場景中AP每次發(fā)送的重傳包的數(shù)量降到理論下限。法律狀態(tài)法律狀態(tài)公告日法律狀態(tài)信息法律狀態(tài)

權(quán)利要求說明書1.無線局域網(wǎng)內(nèi)組播場景中最小丟包重傳方法，其特征在于：

組播網(wǎng)絡(luò)中AP同時(shí)為P個(gè)用戶服務(wù)，廣播N個(gè)原始數(shù)據(jù)包；

每個(gè)用戶分別生成接收狀態(tài)向量，并向AP反饋丟包情況，其中單個(gè)用戶 丟失的數(shù)據(jù)包數(shù)量至多為K；

AP根據(jù)P個(gè)用戶反饋的丟包情況生成一個(gè)P×N的丟包信息統(tǒng)計(jì)矩陣；AP 生成一個(gè)N×K的編碼矩陣，其中編碼矩陣中的每一列代表一個(gè)重傳數(shù)據(jù)包的組 合情況，所有用戶的丟包序號(hào)與編碼矩陣相對(duì)應(yīng)的行向量形成的子矩陣滿秩，且 不影響其他子矩陣的秩；AP將生成的編碼矩陣與原始數(shù)據(jù)包進(jìn)行比特按位異或， 得出組合重傳包并向P個(gè)用戶進(jìn)行廣播；

每個(gè)用戶分別接收所述組合重傳包，并將所述組合數(shù)據(jù)包與該用戶已正確接 收到的數(shù)據(jù)包進(jìn)行異或解碼，恢復(fù)出所丟失的數(shù)據(jù)包。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，該方法適用于具有反向反饋 鏈路的無線多播系統(tǒng)。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于所述編碼矩陣的生成具體包括 以下步驟：

步驟101：從編碼矩陣M中提取第i號(hào)用戶的子矩陣SM；具體地，從丟 包矩陣表中查得第i號(hào)用戶丟包序號(hào)，從編碼矩陣M中提取出丟包序號(hào)對(duì)應(yīng) 的行向量組合成該用戶的編碼子矩陣SM；

步驟102：計(jì)算SM的行數(shù)r、列數(shù)c和秩rank；如果rank等于0則進(jìn) 行步驟103；如果0<rank<r則進(jìn)行步驟104；否則進(jìn)行步驟113；

步驟103：將SM賦值為單位陣，根據(jù)SM更新M相應(yīng)的行向量；

步驟104：判斷子矩陣SM是否有全零行zr和全零列zc；是則進(jìn)行步驟 105，否則進(jìn)行步驟106。

步驟105：將SM內(nèi)第一個(gè)全零行和第一個(gè)全零列交叉處的元素值置1， 進(jìn)行步驟111。

步驟106：令j＝1，其中j是子矩陣SM的列號(hào)；

步驟107：將SM第j列中的零值置1，并重新計(jì)算秩rank；

步驟108：判斷rank是否增加，是則進(jìn)行步驟110，否則進(jìn)行步驟109。

步驟109：令j＝j(luò)+1，返回步驟107。

步驟110：判斷是否影響其他用戶的秩，是則進(jìn)行步驟109，否則進(jìn)行 步驟111；

步驟111：更新M和SM；具體地，根據(jù)SM更新M相應(yīng)的行向量。

步驟112：判斷更新后的子矩陣SM的秩rank的大小是否等于r；如果 等于則進(jìn)行步驟113，否則進(jìn)行步驟114。

步驟113：判斷i是否大于用戶總數(shù)；是則結(jié)束，否則進(jìn)行步驟114。

步驟114：令i＝i+1。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述不影響其他子矩陣的 秩的判斷步驟包括：

步驟201：查看步驟107中置1的數(shù)值所對(duì)應(yīng)的數(shù)據(jù)包編號(hào)m；

步驟202：找出所述丟包信息統(tǒng)計(jì)矩陣含有m的所有用戶的集合S，以及 S中用戶總數(shù)k。

步驟203：令u＝1，jump＝1；u代表S內(nèi)的用戶編號(hào)；jump是程序的返 回值；

步驟204：提取用戶u對(duì)應(yīng)的子矩陣SM，計(jì)算其行值h和秩rank；

步驟205：判斷rank＝h是否成立，是則進(jìn)行步驟207，否則進(jìn)行步驟206；

步驟206：令jump＝-1；

步驟207：判斷u＝k是否成立，是則進(jìn)行步驟209，否則進(jìn)行步驟208；

步驟208：令u＝u+1；

步驟209：返回jump的值；其中，jump的值為1，則不影響其他子矩陣 的秩；jump的值為-1，則影響其他子矩陣中至少一個(gè)子矩陣的秩。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述進(jìn)行異或解碼包括以 下步驟：

步驟301：用戶生成接收狀態(tài)向量并反饋丟包；其中，如果正確接收到 原始數(shù)據(jù)包i，則將接收狀態(tài)向量中第i個(gè)值置1，否則置0；

步驟302：用戶統(tǒng)計(jì)接收到的AP所發(fā)送的異或組合包總個(gè)數(shù)，K的初始 值置為該異或組合包總個(gè)數(shù)；

步驟303：判斷組合包包頭是否含有接收狀態(tài)向量中置0的包號(hào)，是則 進(jìn)行步驟305，否則進(jìn)行步驟304；

步驟304：丟棄該組合包，更新K；

步驟305：令j＝1，其中j代表當(dāng)前的異或組合包序號(hào)；

步驟306：將組合包j與已正確接收的數(shù)據(jù)包異或，并修改組合包包頭； 具體地，將組合包中包頭標(biāo)志位為1且接收狀態(tài)向量中置1的已正確接收的 數(shù)據(jù)包與組合包異或，并將包頭標(biāo)志位中參與異或的數(shù)據(jù)包的包頭標(biāo)志位置 0；

步驟307：判斷當(dāng)前組合包包頭標(biāo)志位是否只有一個(gè)1，是則進(jìn)行步驟 308，否則進(jìn)行步驟310；

步驟308：將當(dāng)前組合包包頭標(biāo)志位對(duì)應(yīng)的數(shù)據(jù)包的接收狀態(tài)向量的值 置1，并令K＝K-1；

步驟309：判斷K＝0是否成立，是則進(jìn)行步驟312，否則進(jìn)行步驟305；

步驟310：判斷j＝K是否成立，是則進(jìn)行步驟312，否則進(jìn)行步驟311；

步驟311：令j＝j(luò)+1；

步驟312：判斷接收狀態(tài)向量是否有0值，是則進(jìn)行步驟313，否則進(jìn) 行步驟314；

步驟313：檢查接收狀態(tài)向量中的0值，并反饋丟包信息；

步驟314：反饋ACK。

說明書<p>技術(shù)領(lǐng)域

本發(fā)明屬于無線通信技術(shù)領(lǐng)域，特別涉及一種具有反饋鏈路的組播場景丟包 恢復(fù)中生成最少數(shù)量重傳包的方法。

背景技術(shù)

信息高效可靠傳輸問題是任意通信系統(tǒng)都需要研究的重要問題。很多應(yīng)用要 求完全可靠的傳輸數(shù)據(jù)，即不能有數(shù)據(jù)包的丟失，例如文件傳輸，財(cái)務(wù)應(yīng)用，電 子郵件，遠(yuǎn)程主機(jī)訪問等應(yīng)用。丟失文件數(shù)據(jù)或財(cái)務(wù)交易數(shù)據(jù)的后果嚴(yán)重。與有 線網(wǎng)絡(luò)相比，在無線通信網(wǎng)絡(luò)中，有很多因素例如衰落、干擾、多徑效應(yīng)和碰撞 會(huì)導(dǎo)致無線傳輸丟包率增高，這就增加了傳輸?shù)拈_銷，而這種開銷在無線組播場 景中是比較嚴(yán)重的。目前，無線傳輸系統(tǒng)中都是采用直接重傳的方式，即每個(gè)用 戶丟什么包就向該用戶重傳該包。例如在一個(gè)AP同時(shí)為三個(gè)用戶服務(wù)的組播系 統(tǒng)中，AP廣播了三個(gè)數(shù)據(jù)包P1、P2和P3，用戶一丟失P1，用戶二丟失P2，用 戶三丟失P3，根據(jù)現(xiàn)有802.11機(jī)制需要向用戶一重傳P1，向用戶二重傳P2， 向用戶三重傳P3，所以AP需要廣播三個(gè)重傳包。當(dāng)組播網(wǎng)絡(luò)內(nèi)用戶增加，鏈路 狀況的差異會(huì)造成各個(gè)用戶丟包不同且極度分散，尤其是在高密度情況下，傳統(tǒng) 的丟包恢復(fù)機(jī)制會(huì)導(dǎo)致重傳包的數(shù)量極大，嚴(yán)重的增加了系統(tǒng)的開銷，傳輸效率 大大降低。當(dāng)信道條件很差或者網(wǎng)絡(luò)很擁堵的情況下，這樣極低的傳輸效率會(huì)導(dǎo) 致重傳次數(shù)增加，時(shí)延加大，甚至傳輸失敗。因此，對(duì)無線傳輸系統(tǒng)組播場景下 的丟包恢復(fù)進(jìn)行最優(yōu)化研究無疑具有重要意義。

近些年提出了一種基于網(wǎng)絡(luò)編碼的組播重傳方法，AP只需要重傳一個(gè)數(shù)據(jù) 包，即將P1、P2和P3進(jìn)行異或組合操作形成異或組合包Q。用戶一將Q與已正 確接收到的P2、P3進(jìn)行異或解碼則可以恢復(fù)出丟包P1，同理用戶二和用戶三也 能以相應(yīng)的方式恢復(fù)出各自丟包。許多無線傳輸系統(tǒng)中基于網(wǎng)絡(luò)編碼的組播重傳 策略的研究已經(jīng)開展。Nguyen等人和Tran等人在《Wireless

Broadcast

Using

Network

Coding》提出了一種無線組播中基于網(wǎng)絡(luò)編碼的丟包重傳策略，發(fā)送節(jié) 點(diǎn)根據(jù)接收節(jié)點(diǎn)反饋的丟包信息，機(jī)會(huì)的選擇不同接收節(jié)點(diǎn)丟失的數(shù)據(jù)包進(jìn)行編 碼，進(jìn)而使得不同的接收節(jié)點(diǎn)在正確接收到編碼重傳數(shù)據(jù)包后，能恢復(fù)出其丟失 的數(shù)據(jù)包。然而這種方法靈活性不好，不能在無線多播場景下根據(jù)各個(gè)接收節(jié)點(diǎn) 的實(shí)際情況發(fā)送其需要的重傳數(shù)據(jù)包，僅僅將一個(gè)無線多播數(shù)據(jù)幀內(nèi)的所有數(shù)據(jù) 包先按照一定方式進(jìn)行編碼再廣播給所有接收節(jié)點(diǎn)，對(duì)于丟包較少的接收節(jié)點(diǎn)， 會(huì)接收到大量多余的重傳數(shù)據(jù)包。中南大學(xué)肖瀟等人在《一種低丟包率無線網(wǎng)絡(luò) 中基于網(wǎng)絡(luò)編碼的廣播重傳方法》和《基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)廣播重傳方法》 中提出了基于網(wǎng)絡(luò)編碼的無線網(wǎng)絡(luò)廣播重傳方法(BRANC),對(duì)將每個(gè)用戶的i 號(hào)丟包異或組合形成重傳包依次發(fā)送，如果無法恢復(fù)出丟包則更換組合方式再次 發(fā)送。使用該方法不能保證系統(tǒng)內(nèi)重傳包數(shù)量最低，而且重傳次數(shù)較多。在某些 特殊丟包情況下這種機(jī)制不能保證所有接收節(jié)點(diǎn)都能恢復(fù)出丟失的數(shù)據(jù)包，因?yàn)? 采用這種機(jī)制的編碼方案，不能保證重傳包之間是線性獨(dú)立的，因此導(dǎo)致重傳包 數(shù)量增多和重傳次數(shù)增加。北京郵電大學(xué)曹震的碩士論文中基于包比特移位設(shè)計(jì) 了一種改進(jìn)范德蒙矩陣的編碼方案，運(yùn)用此方案能夠保證發(fā)送最少編碼重傳數(shù)據(jù) 包后，所有接收節(jié)點(diǎn)都能恢復(fù)出丟失的數(shù)據(jù)包。但是這種方案在接收端恢復(fù)丟包 時(shí)的復(fù)雜度極大，并且數(shù)據(jù)包中一旦有一個(gè)比特位發(fā)生誤碼，此誤碼會(huì)嚴(yán)重蔓延。 本申請(qǐng)人之前也提出過相關(guān)申請(qǐng)CN201410097774.0，提出了組播場景下丟包重 傳機(jī)制的框架和流程，以及重傳包幀格式的設(shè)計(jì)。該申請(qǐng)中使用的生成異或組合 包的方法是將每個(gè)用戶的第i個(gè)丟包異或組合生成第i個(gè)重傳包，此方法在某些 特殊丟包情況下無法保證重傳包之間線性無關(guān)，因而用戶無法正確恢復(fù)出丟包。 例如一個(gè)AP向四個(gè)用戶廣播了四個(gè)數(shù)據(jù)包P1、P2、P3和P4，用戶一丟失P1、 P2，用戶二丟失P1、P4，用戶三丟失P2、P3，用戶四丟失P1、P4。根據(jù)該申請(qǐng) 中的方法生成的重傳包為P1⊕P2⊕P3和P2⊕P3⊕P4，對(duì)于用戶三來說，根據(jù)重 傳包和自身已接收到的數(shù)據(jù)包無法正確恢復(fù)出任何丟包。利用上述BRANC的方法 可以正確恢復(fù)出丟包，但是需要發(fā)送三個(gè)重傳包P1⊕P2⊕P3、P2⊕P3⊕P4和P1 ⊕P2，因此重傳包數(shù)量并不是最低。

為此，本發(fā)明設(shè)計(jì)了一種多播場景下最小丟包重傳方法，這種方法適用于所 有丟包情況。對(duì)于上文所述的丟包情況，根據(jù)本發(fā)明的編碼方法得到的重傳包為 P1⊕P3和P2⊕P4，AP將重傳包數(shù)量壓縮到二個(gè)。本發(fā)明可以保證在所有用戶成 功恢復(fù)出丟包的情況下，AP每次生成的重傳包數(shù)量低至理論最低值。并且，由 于本發(fā)明編碼和解碼都是簡單地進(jìn)行比特按位異或操作，因此編譯碼復(fù)雜度均很 低，額外硬件開銷幾乎為零。

發(fā)明內(nèi)容

為了解決上述技術(shù)問題，本發(fā)明提供了一種具有反饋鏈路的組播場景中最小 丟包重傳方法，運(yùn)用原始數(shù)據(jù)包的按位異或獲得重傳包，在使得所有的接收端都 能正確的恢復(fù)出丟包的情況下，發(fā)送的重傳數(shù)據(jù)包達(dá)到理論最小值。

本發(fā)明提供的一種具有反饋鏈路的組播場景中最小丟包重傳方法，其中，

組播網(wǎng)絡(luò)中AP同時(shí)為P個(gè)用戶服務(wù)，廣播N個(gè)原始數(shù)據(jù)包；

每個(gè)用戶分別生成接收狀態(tài)向量，并向AP反饋丟包情況，其中單個(gè)用戶 丟失的數(shù)據(jù)包數(shù)量至多為K；

AP根據(jù)P個(gè)用戶反饋的丟包情況生成一個(gè)P×N的丟包信息統(tǒng)計(jì)矩陣；AP 生成一個(gè)N×K的編碼矩陣，其中編碼矩陣中的每一列代表一個(gè)重傳數(shù)據(jù)包的組 合情況，所有用戶的丟包序號(hào)與編碼矩陣相對(duì)應(yīng)的行向量形成的子矩陣滿秩，且 不影響其他子矩陣的秩；AP將生成的編碼矩陣與原始數(shù)據(jù)包進(jìn)行比特按位異或， 得出組合重傳包并向P個(gè)用戶進(jìn)行廣播；

每個(gè)用戶分別接收所述組合重傳包，并將所述組合數(shù)據(jù)包與該用戶已正確接 收到的數(shù)據(jù)包進(jìn)行異或解碼，恢復(fù)出所丟失的數(shù)據(jù)包。

本發(fā)明除了給出該技術(shù)方案的具體實(shí)施例以外，還給出了給無線廣播網(wǎng)絡(luò)最 小丟包重傳方法的一個(gè)應(yīng)用實(shí)例。

附圖說明

下面將通過參照附圖詳細(xì)描述本發(fā)明的示例性實(shí)施例，使本領(lǐng)域的普通技術(shù) 人員更清楚本發(fā)明的上述及其它特征和優(yōu)點(diǎn)，附圖中：

圖1為本發(fā)明中AP產(chǎn)生異或組合重傳包的編碼流程圖。

圖2為本發(fā)明判斷修改編碼矩陣是否影響其它用戶的秩的流程圖。

圖3為本發(fā)明中用戶進(jìn)行異或解碼恢復(fù)出丟包的解碼流程圖。

圖4為本發(fā)明中使用最小丟包重傳方法的組播場景重傳機(jī)制的示意圖。

圖5為本發(fā)明中AP生成編碼矩陣以及異或組合包的具體實(shí)例說明圖。

圖6為本發(fā)明中用戶根據(jù)異或組合包進(jìn)行異或解碼恢復(fù)出丟包的具體實(shí)例 說明圖。

具體實(shí)施方式

下面結(jié)合附圖對(duì)本發(fā)明作進(jìn)一步詳細(xì)描述。

圖1為本發(fā)明中AP產(chǎn)生異或組合重傳包的編碼流程圖，具體流程如下：

步驟101：從編碼矩陣M中提取第i號(hào)用戶的子矩陣SM。具體地，從丟 包矩陣表中查得第i號(hào)用戶丟包序號(hào)，從編碼矩陣M中提取出丟包序號(hào)對(duì)應(yīng) 的行向量組合成該用戶的編碼子矩陣SM。

步驟102：計(jì)算SM的行數(shù)r、列數(shù)c和秩rank。如果rank等于0則進(jìn)行 步驟103；如果0<rank<r則進(jìn)行步驟104；否則進(jìn)行步驟113。

步驟103：將SM賦值為單位陣，更新M。此時(shí)子矩陣SM秩為r且對(duì)其他 用戶的秩不造成影響，用SM更新M對(duì)應(yīng)的行向量。

步驟104：判斷子矩陣SM是否有全零行zr和全零列zc。有則進(jìn)行步驟 105，否則進(jìn)行步驟106。

步驟105：將SM內(nèi)第一個(gè)全零行和第一個(gè)全零列交叉處的元素值置1。 進(jìn)行步驟111。

步驟106：令j＝1。j＝1代表子矩陣的第1列，j是子矩陣列號(hào)。

步驟107：將SM中j列零值分別置1，計(jì)算秩rank。該步驟是通過將SM 的零值修改為1來增加其秩大小。

步驟108：判斷rank是否增加，是則進(jìn)行步驟110，否則進(jìn)行步驟109。

步驟109：令j＝j(luò)+1，即對(duì)子矩陣SM的下一列進(jìn)行處理，返回步驟107。

步驟110：判斷是否影響其他用戶的秩，是則進(jìn)行步驟109，否則進(jìn)行步 驟111。該判斷可以通過提取出相關(guān)用戶的子矩陣，重新計(jì)算其秩大小來判 斷修改當(dāng)前零值是否會(huì)影響其他用戶的秩。具體過程由步驟201至209來說 明。

步驟111：更新M和SM。具體地，根據(jù)SM更新M對(duì)應(yīng)的行向量。

步驟112：判斷更新后的子矩陣SM的秩rank的大小是否等于r。如果等 于則進(jìn)行步驟113，否則進(jìn)行步驟104。

步驟113：判斷i是否大于用戶總數(shù)，即判斷是否已對(duì)所有用戶進(jìn)行完賦 值操作。是則進(jìn)行步驟115，否則進(jìn)行步驟114。

步驟114：令i＝i+1，即對(duì)下一個(gè)用戶進(jìn)行以上賦值操作。

步驟115：結(jié)束。

通過以上步驟對(duì)所有用戶進(jìn)行賦值完畢，將本流程所得到的編碼矩陣與原 始數(shù)據(jù)包進(jìn)行比特按位異或便可得出組合重傳包。

圖2為本發(fā)明判斷修改編碼矩陣是否影響其它用戶的秩的流程圖，具體流程 如下：

步驟201：查看修改的數(shù)值所對(duì)應(yīng)的數(shù)據(jù)包編號(hào)m。具體地，在步驟107 中對(duì)子矩陣SM的j列中的某一零值置1，查看該零值對(duì)應(yīng)的行代表的數(shù)據(jù)包 編號(hào)m。

步驟202：找出丟包矩陣含有m的所有用戶集合S，以及S中用戶總數(shù)k。

步驟203：令u＝1，jump＝1。u代表S內(nèi)的用戶編號(hào)；jump是程序的返 回值，用來判斷是否影響S內(nèi)用戶的秩大小。

步驟204：提取用戶u對(duì)應(yīng)的子矩陣SM，計(jì)算其行值h和秩rank。

步驟205：判斷rank＝h是否成立，即判斷用戶u的子矩陣的秩是否等于 其行值。是則進(jìn)行步驟207，否則進(jìn)行步驟206。

步驟206：令jump＝-1，即將-1賦值給jump。

步驟207：判斷u＝k是否成立，即判斷是否已處理完所有用戶。是則進(jìn) 行步驟209，否則進(jìn)行步驟208。

步驟208：令u＝u+1，即對(duì)下一個(gè)用戶進(jìn)行處理。

步驟209：返回jump的值。jump的值為1，表示對(duì)S內(nèi)用戶的秩無影響； jump的值為-1，則該對(duì)當(dāng)前零值的修改影響了某一用戶的秩。

圖3為本發(fā)明中用戶進(jìn)行異或解碼恢復(fù)出丟包的解碼流程圖，具體流程如 下：

步驟301：用戶生成接收狀態(tài)向量并反饋丟包。用戶在收到AP廣播的原 始數(shù)據(jù)包后，根據(jù)自身接收情況生成接收狀態(tài)向量，如果正確接收到原始數(shù) 據(jù)包i，則將向量中第i個(gè)值置1，否則將第i個(gè)值置0。

步驟302：用戶統(tǒng)計(jì)接收到的AP所發(fā)送的異或組合包總個(gè)數(shù)K。

步驟303：判斷組合包包頭是否含有接收向量中置0的包號(hào)，是則進(jìn)行 步驟305，否則進(jìn)行步驟304。其中，接收向量中第i個(gè)值置0代表用戶未 正確接收數(shù)據(jù)包i，如果組合包包頭中包含未正確接收的數(shù)據(jù)包i，則將組 合包放入緩沖區(qū)待處理，否則直接丟棄。

步驟304：丟棄該組合包，更新組合包總個(gè)數(shù)K。

步驟305：令j＝1。j代表當(dāng)前的異或組合包序號(hào)。

步驟306：將組合包j與已正確接收的數(shù)據(jù)包異或，并修改組合包包頭。 具體地，將組合包中包頭標(biāo)志位為1且接收向量中置1的數(shù)據(jù)包與組合包異 或，并將包頭標(biāo)志位中參與異或的數(shù)據(jù)包的包頭標(biāo)志位置0。

步驟307：判斷當(dāng)前組合包包頭標(biāo)志位是否只有一個(gè)1，是則進(jìn)行步驟 308，否則進(jìn)行步驟310。

步驟308：將該標(biāo)志位對(duì)應(yīng)的數(shù)據(jù)包的接收狀態(tài)向量的值置1，并令 K＝K-1。其中，組合包包頭標(biāo)志位只有一個(gè)1，表示該組合包經(jīng)過異或解碼之 后就會(huì)變成原始數(shù)據(jù)包，即包頭標(biāo)志位為1的數(shù)據(jù)包。

步驟309：判斷K＝0是否成立，是則進(jìn)行步驟312，否則進(jìn)行步驟305。 K等于0表示沒有待處理的異或組合包。

步驟310：判斷j＝K是否成立，是則進(jìn)行步驟312，否則進(jìn)行步驟311。 j等于K表示已經(jīng)對(duì)所有的組合包進(jìn)行解碼處理。

步驟311：令j＝j(luò)+1，即已對(duì)j號(hào)組合包進(jìn)行異或解碼，跳轉(zhuǎn)到對(duì)下一 個(gè)組合包進(jìn)行處理。

步驟312：判斷接收狀態(tài)向量是否有0值，是則進(jìn)行步驟313，否則進(jìn) 行步驟314。其中，接收狀態(tài)向量中有0值表示0值代表的數(shù)據(jù)包仍未正確 接收。

步驟313：檢查接收狀態(tài)向量中的0值，并反饋丟包信息。

步驟314：反饋ACK。接收狀態(tài)向量中沒有0值，則代表所有數(shù)據(jù)包已 經(jīng)成功接收，反饋正確應(yīng)答ACK。

圖4為本發(fā)明中使用最小丟包重傳方法的組播場景重傳機(jī)制的示意圖，具體 流程如下：

首先，在一個(gè)AP四個(gè)用戶的組播場景中，AP廣播一組數(shù)據(jù)包P1、P2、P3、 P4、P5、P6。由于四個(gè)組播用戶所處的位置不同導(dǎo)致四個(gè)用戶無線信道差異，所 以各自正確接收到的數(shù)據(jù)包不同。用戶一正確接收了數(shù)據(jù)包P3、P4、P6；用戶 二正確接收了數(shù)據(jù)包P1、P4、P5；用戶三正確接收了數(shù)據(jù)包P1、P2、P5、P6； 用戶四正確接收了數(shù)據(jù)包P1、P2、P3。每個(gè)用戶臨時(shí)生成了自己的接收狀態(tài)向 量，數(shù)據(jù)包被正確接收則將向量對(duì)應(yīng)值置1否則置0。

其次，四個(gè)用戶根據(jù)各自接收情況反饋丟包信息。AP收到如下丟包反饋： 用戶一反饋丟包P1、P2、P5；用戶二反饋丟包P2、P3、P6；用戶三反饋丟包P3、 P4；用戶四反饋丟包P4、P5、P6。AP根據(jù)三個(gè)用戶的丟包反饋信息臨時(shí)生成一 個(gè)丟包統(tǒng)計(jì)表。

最后，AP根據(jù)丟包統(tǒng)計(jì)表，按照本發(fā)明中的編碼方法生成異或組合重傳包， 重傳包Q1由P1、P3、P5按位異或得出，重傳包Q2由P2、P4按位異或得出，重 傳包Q3由P5、P6按位異或得出。由于所有用戶最大丟包個(gè)數(shù)為3，所以AP此 時(shí)只需生成三個(gè)重傳包。各個(gè)用戶根據(jù)本發(fā)明中的解碼方法將異或組合重傳包與 自己已經(jīng)成功接收的數(shù)據(jù)包做相應(yīng)的異或解碼即可恢復(fù)出丟包。

圖5為本發(fā)明中AP生成編碼矩陣以及異或組合包的具體實(shí)例說明圖。

在上述AP和四個(gè)用戶的組播場景中，AP廣播六個(gè)數(shù)據(jù)包后根據(jù)用戶反饋的 丟包情況生成丟包統(tǒng)計(jì)表，由于單個(gè)用戶最大丟包個(gè)數(shù)為3，所以AP生成一個(gè) 6×3的編碼矩陣M，初始化為全零陣。

用戶一丟包P1、P2、P5，提取出編碼矩陣的1、2、5行形成用戶一的子矩 陣SM。此時(shí)SM為全零陣，將SM賦值為單位陣，然后再用SM更新M的1、2、5 行。

用戶二丟包P2、P3、P6，提取出編碼矩陣的2、3、6行形成用戶二的子矩 陣SM。此時(shí)SM秩為1，小于行值3，且有全零行3、6和全零列Q1、Q3。首先將 3行Q1列值的置1，SM秩增加但是仍然小于行值；經(jīng)檢測仍有全零行6和全零 列Q3，然后將6行Q3列值置1，SM滿秩；最后再用SM更新M的2、3、6行。

用戶三丟包P3、P4，提取出編碼矩陣的3、4行形成用戶三的子矩陣SM。此 時(shí)SM只有3行Q1列值為1，小于行值2，且有全零行4和全零列Q2、Q3。首先 將4行Q2列的值置1，SM滿秩；然后再用SM更新M的3、4行。

用戶四丟包P4、P5、P6，提取出編碼矩陣的4、5、6行形成用戶二的子矩 陣SM。此時(shí)SM的秩為2，小于行值3，且沒有全零行只有全零列Q1。首先將4 行Q1列值置1，SM秩不增加，此種修改方案不可行。