邵 鵬 飛， 趙 燕 偉，方 朝 曦

（1.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023；2.浙江萬(wàn)里學(xué)院電子信息學(xué)院，浙江 寧波 315100；3.浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，浙江 杭州 310023）

一種基于散列鄰域搜索網(wǎng)絡(luò)編碼的機(jī)會(huì)中繼重傳方法

邵 鵬 飛1，2， 趙 燕 偉3，方 朝 曦2

（1.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023；2.浙江萬(wàn)里學(xué)院電子信息學(xué)院，浙江 寧波 315100；3.浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，浙江 杭州 310023）

在無(wú)線多播網(wǎng)絡(luò)中，傳統(tǒng)的方法沒(méi)有考慮某些接收節(jié)點(diǎn)與源節(jié)點(diǎn)及其他接收節(jié)點(diǎn)之間可能具有更好的鏈路質(zhì)量。 為此提出了一種基于散列鄰域搜索網(wǎng)絡(luò)編碼的機(jī)會(huì)中繼重傳方法，該方法動(dòng)態(tài)選擇數(shù)據(jù)分組接收情況最好的且信道質(zhì)量?jī)?yōu)于源節(jié)點(diǎn)的接收節(jié)點(diǎn)作為中繼，并采用散列鄰域搜索網(wǎng)絡(luò)編碼策略進(jìn)行其他接收節(jié)點(diǎn)的丟失分組重傳。 仿真結(jié)果表明，相對(duì)于現(xiàn)有的其他網(wǎng)絡(luò)編碼重傳方法，該方法能有效減少平均重傳次數(shù)，提高重傳效率，尤其當(dāng)一些接收節(jié)點(diǎn)因受到干擾與源節(jié)點(diǎn)之間的信道質(zhì)量變得很差時(shí)，該方法能取得很高的重傳增益。

無(wú)線多播；網(wǎng)絡(luò)編碼；機(jī)會(huì)中繼；重傳

1 引言

隨著通信技術(shù)的進(jìn)步和發(fā)展及泛在物聯(lián)網(wǎng)物與物之間 的 智 能 互 聯(lián) 和 大 規(guī) 模 分 布 式 計(jì) 算［1，2］，越 來(lái) 越 多 的 網(wǎng) 絡(luò) 應(yīng)用和服務(wù)滲透到日常生活中。在物聯(lián)網(wǎng)基礎(chǔ)架構(gòu)中，除了物理基礎(chǔ)設(shè)施外，基于通信網(wǎng)絡(luò)收集和交換各種有用的信息才能充分發(fā)揮物聯(lián)網(wǎng)的優(yōu)勢(shì)。無(wú)線通信系統(tǒng)是物聯(lián)網(wǎng)中最重要的基礎(chǔ)通信網(wǎng)絡(luò)之一，使用越來(lái)越廣泛。由于無(wú)線通信系統(tǒng)的傳輸可靠性較低，重傳技術(shù)一直是該領(lǐng)域研究的 重 點(diǎn)［3，4］。

在無(wú)線多播網(wǎng)絡(luò)中，基于傳統(tǒng)的直接重傳方式，比如ARQ 或 HARQ［5］等 ，源 節(jié) 點(diǎn) 逐 個(gè) 重 傳 各 接 收 節(jié) 點(diǎn) 丟 失 的 數(shù)據(jù)分組，傳輸效率低、能耗大。利用信道的廣播特性，基于網(wǎng)絡(luò)編碼的廣播重傳已被證明能有效減少平均重傳次數(shù)，提 升 傳 輸 性 能［6-8］。該 方 式 下 ，源 節(jié) 點(diǎn) 根 據(jù) 各 接 收 節(jié) 點(diǎn) 不 同的數(shù)據(jù)分組丟失情況，對(duì)丟失分組進(jìn)行調(diào)度和優(yōu)化組合后編碼重傳，每一次重傳能夠同時(shí)讓盡量多的接收節(jié)點(diǎn)恢復(fù)其丟失分組，從而減少總的重傳次數(shù)。盡管相對(duì)于傳統(tǒng)的直接重傳方式，基于網(wǎng)絡(luò)編碼的重傳技術(shù)大大提高了傳輸效率，降低了傳輸能耗，但是目前主要的研究都是假設(shè)信道 相 互 獨(dú) 立 且 信 道 狀 態(tài) 不 變［9-11］，沒(méi) 有 考 慮 無(wú) 線 鏈 路 狀 態(tài)的實(shí)時(shí)變化及這些變化對(duì)重傳增益的影響，與實(shí)際網(wǎng)絡(luò)情況 仍 有 較 大 的 差 距 。參 考 文 獻(xiàn)［12］雖 然 考 慮 了 每 個(gè) 節(jié) 點(diǎn) 接收鏈路分組丟失率的不同，提出了基于機(jī)會(huì)網(wǎng)絡(luò)編碼的加權(quán)廣播重傳方法，將減少重傳次數(shù)轉(zhuǎn)化為基于加權(quán)的最大增益問(wèn)題，但當(dāng)源節(jié)點(diǎn)與某接收節(jié)點(diǎn)的信道質(zhì)量變差時(shí)，重傳性能將快速惡化。

在無(wú)線中繼網(wǎng)絡(luò)中，通過(guò)中繼協(xié)作轉(zhuǎn)發(fā)信息，可以有效利用信道并獲得分集增益，提高傳輸可靠性。將機(jī)會(huì)中繼協(xié)作傳輸技術(shù)應(yīng)用于重傳，利用質(zhì)量較好的無(wú)線信道實(shí)現(xiàn)中繼重傳，能有效提升重傳性能。但對(duì)中繼協(xié)作通信的研 究 目 前 主 要 集 中 于 單 源 — 單 中 繼 — 兩 目 的［13］、兩 源 — 單中 繼 — 兩 目 的［8，14］、兩 源 — 單 中 繼 — 單 目 的［15］等 中 繼 通 信 系統(tǒng)，在單跳無(wú)線網(wǎng)絡(luò)中很少提及。

為此，本文提出了一種適合單跳多播網(wǎng)絡(luò)的基于散列鄰 域 搜 索 網(wǎng) 絡(luò) 編 碼 的 機(jī) 會(huì) 中 繼 重 傳 （hash neighborhood search network coding opportunistic relaying retransmission，HNS-NCORR）方法。該方法充分考慮節(jié)點(diǎn)之間的信道質(zhì)量，動(dòng)態(tài)選擇數(shù)據(jù)分組接收情況最好的且信道質(zhì)量?jī)?yōu)于源節(jié)點(diǎn)的接收節(jié)點(diǎn)作為中繼，進(jìn)行其他接收節(jié)點(diǎn)的丟失分組重傳，重傳方法基于散列鄰域搜索網(wǎng)絡(luò)編碼策略。與現(xiàn)有的網(wǎng)絡(luò)編碼重傳方法相比，這種結(jié)合機(jī)會(huì)中繼的網(wǎng)絡(luò)編碼重傳方法由于選擇了信道質(zhì)量更好的鏈路進(jìn)行重傳，提高了每一次重傳的效率，從而能夠提高整體的傳輸性能，尤其當(dāng)個(gè)別接收節(jié)點(diǎn)由于受到干擾與源節(jié)點(diǎn)之間的信道質(zhì)量變得非常差時(shí)，其作用將更加明顯。

2 系統(tǒng)模型

如 圖 1 所 示，本 文基 于 通 用 的 無(wú) 線 多 播模 型 ，一 個(gè) 源節(jié) 點(diǎn) S 和 N 個(gè) 接 收 節(jié) 點(diǎn) Ri（N≥3，1≤i≤N）進(jìn) 行 通 信 。 假定系統(tǒng)采用時(shí)分多址技術(shù)，源節(jié)點(diǎn)和各接收節(jié)點(diǎn)之間的信道相互獨(dú)立，信道環(huán)境變化緩慢，即數(shù)據(jù)重傳時(shí)的信道增益變化可忽略不計(jì)，且反饋信道是可靠的，狀態(tài)信息在反饋信道中不存在丟失。整個(gè)通信過(guò)程分為兩個(gè)階段：初始階段和丟失分組重傳階段。在初始階段，源節(jié)點(diǎn)向接收節(jié)點(diǎn) 逐 個(gè) 廣 播 M 個(gè) 原 始 數(shù) 據(jù) 分 組 Qj（1≤j≤M），各 接 收 節(jié) 點(diǎn)Ri采用 ACK／NACK 同步反饋其丟失分組信息。當(dāng) S 發(fā)送完M 個(gè)數(shù)據(jù)分組后，能得到 N 個(gè)接收節(jié)點(diǎn)的接收狀態(tài)信息。

圖1 通用無(wú)線多播通信系統(tǒng)

在丟失分組重傳階段，根據(jù)節(jié)點(diǎn)間信道狀態(tài)，動(dòng)態(tài)選擇數(shù)據(jù)分組接收情況最好的且信道質(zhì)量?jī)?yōu)于源節(jié)點(diǎn)的接收節(jié)點(diǎn)作為中繼，進(jìn)行其他接收節(jié)點(diǎn)的丟失分組重傳。若不存在這種情況，則直接采用散列鄰域搜索網(wǎng)絡(luò)編碼重傳方 法［11］進(jìn) 行 重 傳 。

機(jī)會(huì)中繼選擇準(zhǔn)則：中繼節(jié)點(diǎn)到目的節(jié)點(diǎn)的鏈路質(zhì)量由中繼節(jié)點(diǎn)到多個(gè)目的節(jié)點(diǎn)的鏈路質(zhì)量中較差的一路決定，而端到端的信道質(zhì)量由源—中繼和中繼—目的信道中質(zhì)量較差的一路決定，最佳中繼節(jié)點(diǎn)擁有最好的端到端的信道質(zhì)量。以鏈路分組丟失率作為衡量鏈路質(zhì)量的指標(biāo)，假設(shè) 接 收 節(jié) 點(diǎn) Ri被 選 為 最 佳 中 繼 節(jié) 點(diǎn) ，PS，Ri為源節(jié)點(diǎn)到 Ri的分 組 丟 失 率 ，PRi，Rk為 Ri到 其 他 接 收 節(jié) 點(diǎn) 的 分 組 丟 失 率 ，PS，Rk為源節(jié)點(diǎn)到其他接收節(jié)點(diǎn)的分組丟失率，則 Ri需滿足：

在具有3個(gè)接收節(jié)點(diǎn)無(wú)線多播網(wǎng)絡(luò)中：

（1）若 唯 一 存 在 符 合 式 （1）的 接 收 節(jié) 點(diǎn) Ri，則 選 擇 Ri作為重傳中繼，并采用本文的 NCORR 方法；

（2）若同時(shí)存在符合式（1）的兩個(gè)接收節(jié)點(diǎn)，則隨機(jī)選擇其一作為重傳中繼，轉(zhuǎn)化為（1）進(jìn)行處理。

在具有多個(gè)（超過(guò) 3 個(gè)）接收節(jié)點(diǎn)的無(wú)線多播網(wǎng)絡(luò)中：

（1）若 唯 一 存 在 符 合 式 （1）的 接 收 節(jié) 點(diǎn) Ri，則 選 擇 Ri作為重傳中繼，并采用本文的 NCORR 方法；

（2）若同時(shí)存在符合式（1）的兩個(gè)接收節(jié)點(diǎn)，則隨機(jī)選擇其一作為重傳中繼，轉(zhuǎn)化為步驟（1）進(jìn)行處理；

（3）若 同 時(shí) 存 在 符 合 式 （1）的 K（K＞2）個(gè) 接 收 節(jié) 點(diǎn) Rj，則按與每個(gè) Rj之間鏈路的信道質(zhì)量按照就高原則進(jìn)行區(qū)域劃分，將重傳 劃 分為 K 個(gè)重 傳 簇；在每個(gè)重 傳 簇 內(nèi)選擇Rj作為重傳中繼，轉(zhuǎn)化為步驟（1）進(jìn)行處理；若某個(gè)重傳簇內(nèi)節(jié)點(diǎn)數(shù)少于 3，則與鄰近重傳簇合并，合并后根據(jù)步驟（1）或（2）進(jìn)行處理。

因 此 ，在 無(wú) 線 多播 網(wǎng) 絡(luò) 中，無(wú) 論是 只 有 3 個(gè) 接 收 節(jié) 點(diǎn)還是具有更多接收節(jié)點(diǎn)，本文的重傳處理思想是相同的，最終都轉(zhuǎn)化為唯一存在符合式（1）的接收節(jié)點(diǎn)的情形進(jìn)行處理。下文中，將以具有 3個(gè)接收節(jié)點(diǎn)的無(wú)線多播網(wǎng)絡(luò)為例，闡述本文的方法。

3 HNS-NCORR 重傳方法

本節(jié)將詳細(xì)闡述提出的基于散列鄰域搜索網(wǎng)絡(luò)編碼的機(jī)會(huì)中繼重傳方法。在單跳無(wú)線多播網(wǎng)絡(luò)中，區(qū)別于其 他 重 傳 方 式 ，HNS-NCORR 動(dòng) 態(tài) 選 擇 具 有 比 源 節(jié) 點(diǎn) 信道質(zhì)量更好的接收節(jié)點(diǎn)作為中繼，進(jìn)行其他接收節(jié)點(diǎn)的丟失分組重傳，從而減少平均重傳次數(shù)，提高重傳效率。對(duì)丟失分組的調(diào)度、組合和編碼采用散列鄰域搜索網(wǎng)絡(luò)編碼策略。

3.1 機(jī)會(huì)中繼策略

具有 3個(gè)接收節(jié)點(diǎn)的無(wú)線多播網(wǎng)絡(luò)如圖 2所示。

圖2 具有3個(gè)接收節(jié)點(diǎn)的無(wú)線多播網(wǎng)絡(luò)

假設(shè)：

由于 R1唯一符合式（1）條件，因此在重傳階段，R1將被選為重傳中繼，其重傳方法如圖 3所示。

情形 1 在初始階段結(jié)束后，若 R1正確接收所有分組，R2和 R3存在分組丟失。此時(shí)，R1采用散列鄰域搜索網(wǎng)絡(luò)編碼策略直接重傳 R2和 R3丟失的數(shù)據(jù)分組，如圖 3（a）所示。

情 形 2 在 初 始 階 段 結(jié) 束 后 ，若 R1、R2和 R3都 存 在 分組丟失，但 R1的接收情況最好且只有少量分組丟失。此時(shí)有兩種處理方法。

方法（1） 首先充分利用 R1成功接收的數(shù)據(jù)分組，R1將自 己成功接收，而 R2和 R3沒(méi) 有正確接 收 的數(shù)據(jù)分 組 進(jìn)行編碼重傳，直至兩節(jié)點(diǎn)都正確接收；然后源節(jié)點(diǎn)編碼重傳剩余的3個(gè)節(jié)點(diǎn)都沒(méi)有正確接收的分組。

方 法 （2） 如 圖 3（b）所 示 ，首 先 源 節(jié) 點(diǎn) 廣 播 重 傳 R1丟失的分組 ，讓 R1正 確接收所有數(shù)據(jù)分組，R2和 R3可同時(shí)接收這些重傳分組來(lái)獲取自己未正確接收的分組；然后選擇 R1作為中繼，編碼重傳 R2和 R3丟失的分組。在可解條 件 下［11］，在 重 傳 R1丟 失 分 組 的 過(guò) 程 中 ，可 組 合 R2、R3丟失的其他數(shù)據(jù)分組進(jìn)行編碼重傳，進(jìn)一步提高編碼增益。由于當(dāng)源節(jié)點(diǎn)S和個(gè)別接收節(jié)點(diǎn)的無(wú)線信道質(zhì)量比較差時(shí) ，方 法（1）仍有可 能 需 要 源 節(jié) 點(diǎn) S 直 接重 傳 該 節(jié) 點(diǎn)丟 失的分組，導(dǎo)致重傳性能快速下降，而方法（2）則不存在這種情況，因此本文將采用方法（2）處理情形 2。

圖3 基于網(wǎng)絡(luò)編碼的機(jī)會(huì)中繼重傳方法

方法（3） 對(duì)于其他情形，直接采用散列鄰域搜索網(wǎng)絡(luò)編碼策略進(jìn)行重傳。

3.2 散列鄰域搜索網(wǎng)絡(luò)編碼重傳

相 對(duì) 于 傳 統(tǒng) 的 網(wǎng) 絡(luò) 編 碼 重 傳 策 略［9，10］，散 列 鄰 域 搜 索 網(wǎng)絡(luò) 編 碼 重 傳 策 略［11］在 對(duì) 丟 失 分 組 的 快 速 調(diào) 度 和 優(yōu) 化 組 合 、重傳再丟失的優(yōu)化處理等方面，有更好的考慮和設(shè)計(jì)，進(jìn)一步提高了重傳效率，其主要過(guò)程如下。

（1）發(fā)送節(jié)點(diǎn)基于接收狀態(tài)表生成各接收節(jié)點(diǎn)丟失分組散列表（接收狀態(tài)表表明發(fā)送節(jié)點(diǎn)有哪些數(shù)據(jù)分組未能被哪些接收節(jié)點(diǎn)正確接收）。

（2）發(fā)送節(jié)點(diǎn)基于散列鄰域搜索快速選擇符合滿秩條件（可解條件下能從單個(gè)重傳數(shù)據(jù)分組中恢復(fù)丟失分組的接收節(jié)點(diǎn)數(shù)達(dá)到最多）的丟失分組或丟失分組組合。

（3）發(fā)送節(jié)點(diǎn)對(duì)選出的丟失分組組合進(jìn)行異或（XOR）編碼，形成新的重傳分組并發(fā)送出去。

（4）發(fā)送節(jié)點(diǎn)基于鄰域關(guān)聯(lián)搜索進(jìn)一步挖掘編碼機(jī)會(huì)，合并成多個(gè)關(guān)聯(lián)的重傳分組，經(jīng) XOR 編碼后發(fā) 送出去，并允許接收節(jié)點(diǎn)從多個(gè)重傳分組中恢復(fù)丟失分組。

（5）各接收節(jié)點(diǎn)從收到的重傳分組中解碼出自己的丟失分組。

HNS-NCORR 對(duì)丟失分組的調(diào)度、組合、編碼采用散 列鄰域搜索網(wǎng)絡(luò)編碼重傳策略。在重傳階段，HNS-NCORR 在完成機(jī)會(huì)中繼選擇后，判斷被選出的中繼節(jié)點(diǎn)是否存在分組丟失。若中繼節(jié)點(diǎn)存在分組丟失，則源節(jié)點(diǎn)首先重傳中繼節(jié)點(diǎn)的丟失分組，重傳時(shí)最大化組合滿足可解條件的其他接收節(jié)點(diǎn)的丟失分組，中繼節(jié)點(diǎn)和其他接收節(jié)點(diǎn)接收該重傳分組并解碼出各自的丟失分組，然后同步反饋接收狀態(tài)信息，源節(jié)點(diǎn)收到這些信息后更新自己的接收狀態(tài)表，直至中繼節(jié)點(diǎn)正確接收所有數(shù)據(jù)分組。若中繼節(jié)點(diǎn)不存在分組丟失或經(jīng)重傳后中繼節(jié)點(diǎn)已正確接收所有數(shù)據(jù)分組，則源節(jié)點(diǎn)將接收狀態(tài)表信息發(fā)送給中繼節(jié)點(diǎn)，中繼節(jié)點(diǎn)收到該信息后生成自己的接收狀態(tài)表（該表只包含其他接收節(jié)點(diǎn)的分組接收狀態(tài)），并根據(jù)此表代替源節(jié)點(diǎn)重傳其他接收節(jié)點(diǎn)丟失的分組，直至其他節(jié)點(diǎn)成功接收所有數(shù)據(jù)分組，然后反饋重傳結(jié)束信息通知源節(jié)點(diǎn)進(jìn)行下一組數(shù)據(jù)分組的傳輸。當(dāng)其他接收節(jié)點(diǎn)從源節(jié)點(diǎn)和中繼節(jié)點(diǎn)都收到某重傳分組時(shí)，采用最大合并比解碼。

由于無(wú)線傳輸?shù)牟豢煽啃?，重傳的分組仍會(huì)丟失。為了在重傳的分組中不再出現(xiàn)已被所有節(jié)點(diǎn)成功接收的數(shù)據(jù)分組，在每次重傳之前，HNS-NCORR 根據(jù)節(jié)點(diǎn)反饋的 接收信息更新接收狀態(tài)表（源節(jié)點(diǎn)重傳則更新源節(jié)點(diǎn)的接收狀態(tài)表，中繼節(jié)點(diǎn)重傳則更新中繼節(jié)點(diǎn)的接收狀態(tài)表）；然后根據(jù)新的接收狀態(tài)表，在余下的丟失分組中通過(guò)散列鄰域搜索和鄰域關(guān)聯(lián)搜索快速查找丟失分組組合，形成新的合并數(shù)據(jù)分組并編碼重傳。這種丟失分組更新機(jī)制由于調(diào)度組合時(shí)結(jié)合了最新的丟失分組信息，創(chuàng)造了更多的編碼機(jī)會(huì)，可以有效提高重傳效率。

3.3 HNS-NCORR 流程

如圖 4 所示，HNS-NCORR 的工作流程分為兩個(gè)階段：在初始階段，源節(jié)點(diǎn)連續(xù)發(fā)送 M個(gè)數(shù)據(jù)分組并判斷接收狀況，若這 M 個(gè)分組被所有節(jié)點(diǎn)成功接收，則發(fā)送之后的 M 個(gè)數(shù)據(jù)分組，否則進(jìn)入重傳階段。在重傳階段，HNS-NCORR 首先根據(jù)分組接收情況和節(jié)點(diǎn)間鏈路狀態(tài)選擇機(jī)會(huì)中繼；若找不到中繼節(jié)點(diǎn)，源節(jié)點(diǎn)則采用散列鄰域搜索網(wǎng)絡(luò)編碼策略重傳所有節(jié)點(diǎn)的丟失分組；若找到中繼節(jié)點(diǎn)，則判斷該中繼節(jié)點(diǎn)是否已成功接收M個(gè)分組；源節(jié)點(diǎn)優(yōu)先重傳中繼節(jié)點(diǎn)的丟失分組，直至中繼節(jié)點(diǎn)成功接收所有分組，然后中繼節(jié)點(diǎn)代替源節(jié)點(diǎn)重傳其他接收節(jié)點(diǎn)的丟失分組。由于中繼節(jié)點(diǎn)具有更好的無(wú)線信道質(zhì)量，因此能取得更好的傳輸增益。

圖4 HNS-NCORR 工作 流 程

4 數(shù)學(xué)分析

在有 N（N≥3）個(gè)接 收節(jié)點(diǎn) 的多 播網(wǎng)絡(luò)中，假 定 N 個(gè)接 收 節(jié) 點(diǎn) 的 分 組 丟 失 率 互 不 相 關(guān) 且 服 從 伯 努 利 分 布［10-12］，令 pi表 示 接 收 節(jié) 點(diǎn) Ri（1≤i≤N）與 源 節(jié) 點(diǎn) S 之 間 的 鏈 路 分組 丟 失 率 ，pm=max｛p1，p2，… ，pN｝，其 中 ，1≤m ≤N，令 λij為 接收節(jié)點(diǎn) Ri和 Rj之間 的鏈路分組丟失率。當(dāng) M 足夠大 時(shí) ，在初始階段的 M 次初始傳輸后，各個(gè)接收節(jié)點(diǎn)分別有 Mpi個(gè)數(shù)據(jù)分組沒(méi)有被正確接收，節(jié)點(diǎn) Rm則是丟失分組最多的節(jié)點(diǎn)，丟失 Mpm個(gè)數(shù)據(jù)分組。在重傳階段，若各個(gè)接收節(jié)點(diǎn)每次正確接收都能獲取 1個(gè)原始分組，則每個(gè)接收節(jié)點(diǎn)正確 接 收 全 部 數(shù) 據(jù) 分 組 所 需 的 重 傳 次 數(shù) 為 Mpi／（1-pi）。由 于pm最大，可 以 得 到 Mpm／（1-pm）最 大 。

（1）當(dāng)數(shù)據(jù)分組數(shù) M 足 夠 大時(shí)，采用基 于 網(wǎng) 絡(luò)編碼的重 傳 方 法［9-12］，每 個(gè) 重 傳 分 組 都 可 以 看 成 鏈 路 分 組 丟 失 率最 大 的 接 收 節(jié) 點(diǎn) 與 其 余 N-1 個(gè) 節(jié) 點(diǎn) 丟 失 分 組 的 編 碼 組合，因此總 的 重 傳次 數(shù) 為 Mpm／（1-pm），由 分 組 丟 失 率 最 大的 節(jié) 點(diǎn) 決 定 。即 M 個(gè) 數(shù) 據(jù) 分 組 的 平 均 重 傳 次 數(shù) TNC［10-13］可表示為：

（2）采用本文的 HNS-NCORR 方法，M 個(gè)數(shù)據(jù)分組的平均 重 傳 次 數(shù) THNS-NCORR可 表 示 為 ：

代入 φ 和 w，并根據(jù)式（5）可得：

因 此 ，當(dāng) ?Pm、Pk、λkm滿 足 式 （7）時(shí) ，HNS-NCORR 方 法比其他基于網(wǎng)絡(luò)編碼的重傳方法進(jìn)一步減少了平均重傳次數(shù)，獲得了更高的傳輸效率。

HNS-NCORR 方法相對(duì)于其他網(wǎng)絡(luò)編碼重 傳方法的重傳增益為：

代入式（3）和式（4），可得：

當(dāng) pm、pk、λkm滿 足 式 （7）時(shí) ，HNS-NCORR 方 法 就 能 獲得 正 重 傳 增 益 。當(dāng) pm遠(yuǎn) 大 于 pk、λkm時(shí) ，即 一 個(gè) 或 一 個(gè) 以 上接收節(jié)點(diǎn)與源節(jié)點(diǎn)之間的無(wú)線鏈路質(zhì)量因干擾變得很差時(shí)，系統(tǒng)將獲得很大的重傳增益。

5 仿真與分析

HNS-NCORR 方法首先根據(jù)鏈路狀態(tài)檢測(cè) 機(jī)制計(jì)算源節(jié)點(diǎn)、各接收節(jié)點(diǎn)之間的鏈路分組丟失率，并根據(jù)鏈路分組丟失率進(jìn)行機(jī)會(huì)中繼選擇，然后采用基于散列鄰域搜索網(wǎng)絡(luò)編碼方法進(jìn)行重傳，重傳分為兩個(gè)階段：首先源節(jié)點(diǎn)重傳中繼節(jié)點(diǎn)的丟失分組，然后中繼節(jié)點(diǎn)代替源節(jié)點(diǎn)重傳其他 接 收 節(jié) 點(diǎn) 的 丟 失 分 組 。參 考 文 獻(xiàn) ［11］提 出 了 改 進(jìn) 的 網(wǎng) 絡(luò)編碼重傳方法 IONCR，該方法在單跳無(wú)線多播網(wǎng)絡(luò)中由源節(jié)點(diǎn)通過(guò)鄰域關(guān)聯(lián)搜索進(jìn)行分組丟失組合和編碼重傳，并優(yōu)先重傳能讓最多接收節(jié)點(diǎn)恢復(fù)其丟失分組的單個(gè)重傳分組，在保持較低算法復(fù)雜度的情況下，相對(duì) 于 ARQ 直接重 傳 及 其 他 網(wǎng) 絡(luò) 編 碼 重 傳 方 法［16，17］，IONCR 能 取 得 更 好 的 重傳性能。為此，在相同的無(wú)線網(wǎng)絡(luò)環(huán)境下，本文直接比較了 HNS-NCORR 算 法 與 IONCR 算 法 的 重 傳 性 能 ，并 以 平均重傳次數(shù)作為重傳性能分析的評(píng)價(jià)指標(biāo)。

仿真中，考慮實(shí)際應(yīng)用環(huán)境，將分別考察兩種系統(tǒng)模型：在 系 統(tǒng) A 中，源節(jié)點(diǎn) 與 所 有接收節(jié) 點(diǎn) 的無(wú)線鏈 路 質(zhì) 量都 較 好；在系統(tǒng) B 中 ，存 在 一個(gè)或一 個(gè) 以上接收 節(jié) 點(diǎn) 與 源節(jié)點(diǎn)之間的無(wú)線信道由于受到干擾導(dǎo)致高鏈路分組丟失率。當(dāng)接收節(jié)點(diǎn)數(shù) N=4 時(shí)，系統(tǒng) A、B 中源節(jié)點(diǎn) 、各接收 節(jié)點(diǎn) 之 間 的 信 道 參 數(shù) 如 下 （ 行 參 數(shù) 為 ［S R1R2R3R4］＇，列 參 數(shù)為［S R1R2R3R4］）：

為了 更好地進(jìn)行 性能比 較，引入中間 系 統(tǒng) C，系 統(tǒng) C與系統(tǒng) B相近但節(jié)點(diǎn)受到的干擾較小。在系統(tǒng) B中，接收節(jié)點(diǎn) R4受到干擾，與源節(jié)點(diǎn)之間的鏈路分組丟失率達(dá)到0.8。在系統(tǒng) C 中，接 收 節(jié) 點(diǎn) R4受 到 的 干 擾 比 系 統(tǒng) B 小 ，與源 節(jié) 點(diǎn) 之 間 的 鏈 路 分 組 丟 失 率 為 0.6。在 3 個(gè) 系 統(tǒng) 中 ，根 據(jù)式（7）和式（1）確定 R1為最佳中繼節(jié)點(diǎn)，與式（10）～式（12）節(jié)點(diǎn)之間的鏈路質(zhì)量情況相符。

圖5 比 較 了 N=4 時(shí) 3 個(gè) 系 統(tǒng) 中 HNS-NCORR 和IONCR 的重傳性能。從仿真結(jié)果可以看到，在 3 個(gè)系統(tǒng)中，HNS-NCORR 的 平 均 重 傳 次 數(shù) 都 要 少 于 IONCR，而 且 當(dāng) 一個(gè)接收節(jié)點(diǎn)至源節(jié)點(diǎn)的鏈路質(zhì)量變壞，出現(xiàn)高分組丟失率時(shí)，這種優(yōu)勢(shì)更加突出。在系統(tǒng) A、C、B 中，根據(jù)式（9）計(jì)算可 得 HNS-NCORR 相 對(duì) 于 IONCR 的 重 傳 增 益 分 別 約 為10%、80%和 300%，與 圖 5 中 仿 真 結(jié) 果 相 符 。 這 是 因 為HNS-NCORR 有效利用了信道質(zhì)量最好的接收節(jié)點(diǎn)進(jìn)行 重傳，當(dāng)某個(gè)接收節(jié)點(diǎn)與源節(jié)點(diǎn)之間的信道變得很差而與機(jī)會(huì)中繼節(jié)點(diǎn)之間的信道保持較好的情況下，將大大提高重傳效率。

圖5 N=4 時(shí)不同網(wǎng)絡(luò)環(huán)境下（好、中、差）重傳性能比較

假 設(shè) N=3 和 N=5 時(shí) ，系 統(tǒng) A 和 系 統(tǒng) B 的 信 道 參 數(shù)如下：

圖6（a）和圖 6（b）分別比較了較好無(wú)線網(wǎng)絡(luò)環(huán)境和受干擾無(wú)線網(wǎng)絡(luò) 環(huán)境下，不 同 接收節(jié)點(diǎn) 數(shù) 時(shí) HNS-NCORR 和IONCR 的重傳性能。從仿真結(jié)果可以看出，無(wú)論在哪種網(wǎng)絡(luò) 環(huán) 境 下 ，HNS-NCORR 的 重 傳 性 能 都 優(yōu) 于 IONCR。 這 是因 為 這 些 模 型 的 參 數(shù) 都 滿 足 式 （5） 的 條 件 ， 所 以HNS-NCORR 的平均重傳次數(shù)要少于 IONCR。 當(dāng)網(wǎng)絡(luò)規(guī)模變大、接收節(jié)點(diǎn)數(shù)增加時(shí)，HNS-NCORR 能保持較穩(wěn)定的重傳性能，在較好的無(wú)線網(wǎng) 絡(luò)環(huán)境下，相對(duì)于 IONCR 有 10%左右的重傳增益；在受干擾較差環(huán)境下，某接收節(jié)點(diǎn)與源節(jié) 點(diǎn) 之 間 出 現(xiàn) 高 鏈 路 分 組 丟 失 率 時(shí) ，相 對(duì) 于 IONCR 有300%左右的重傳增益。

圖6 不同環(huán)境下不同接收節(jié)點(diǎn)數(shù)的重傳性能比較

6 結(jié)束語(yǔ)

在單跳無(wú)線多播網(wǎng)絡(luò)中，現(xiàn)有的網(wǎng)絡(luò)編碼重傳方法普遍選用源節(jié)點(diǎn)進(jìn)行丟失分組重傳，對(duì)節(jié)點(diǎn)之間無(wú)線鏈路的質(zhì)量及其動(dòng)態(tài)變化考慮不足，本文提出了一種基于散列鄰域 搜 索 網(wǎng) 絡(luò) 編 碼 的 機(jī) 會(huì) 中 繼 重 傳 方 法 ——HNS-NCORR，并分析了該方法適用的條件。HNS-NCORR 方法充分考慮了無(wú)線鏈路質(zhì)量及其狀態(tài)的動(dòng)態(tài)變化，利用網(wǎng)絡(luò)中具有更高鏈路質(zhì)量的接收節(jié)點(diǎn)代替源節(jié)點(diǎn)進(jìn)行丟失分組重傳，與現(xiàn)有的網(wǎng)絡(luò)編碼重傳等方法相比，能減少鏈路中斷率，獲得更好的重傳增益。仿真結(jié)果表明，HNS-NCORR 減少了平均重傳次數(shù)，提高了重傳效率，尤其當(dāng)網(wǎng)絡(luò)中一個(gè)或一個(gè)以上接收節(jié)點(diǎn)因受到干擾導(dǎo)致高鏈路分組丟失率時(shí)，該方法的效果更加明顯。

［1］ STOJMENOVIC I.Machine-to-machinecommunicationswith in-network data aggregation， processing， and actuation for large-scale cyber-physical systems ［J］.IEEE Internet of Things Journal，2014，1（2）：122-128.

［2］ CHEN K C，LIEN S Y.Machine-to-machine communications：technologies and challenges ［J］.Ad Hoc Networks，2014 （18）：3-23.

［3］ QURESHI J，F(xiàn)OH C H，CAI J F.An efficient network coding based retransmission algorithm for wireless multicast［C］／IEEE 20th International Symposium on Personal，Indoor and Mobile Radio Communications，September 13-16，2009，Tokyo，Japan. New Jersey：IEEE Press，2009：691-695.

［4］ VIEN Q T， STEWART B G.An efficientcooperative retransmission for wireless regenerative relay networks［C］／2012 IEEE Global Communications Conference （GLOBECOM），December 3-7，2012，California，USA.New Jersey：IEEE Press，2012：4417-4422.

［5］ LEVORATO M，TOMASIN S，ZORZI M.Cooperative spatial multiplexing for ad hoc networks with hybrid ARQ：system design and performance analysis ［J］.IEEE Transactions on Communications，2008（9）：1545-1555.

［6］ HO T，MEDARD M，KOETTER R，et al.A random linear network coding approach to multicast ［J］.IEEE Transactions on Information Theory，2006，52（10）：4413-4430.

［7］TRAN T，NGUYEN T，BOSE B，et al.A hybrid network coding technique for single-hop wireless networks［J］.IEEE Journal on Selected Areas in Communications，2009，27（5）：685-698.

［8］ SONG Q，LI Y，HE Z Q，et al.On reliable multicast with network coding ARQ for relay cooperation cells ［C］／75th IEEE Vehicular Technology Conference （VTC Spring），May 6-9，2012，Yokohama，Japan.New Jersey：IEEE Press，2012：1-5.

［9］ SOROUR S， VALAEE S.An adaptive network coded retransmission scheme for single-hop wireless multicast broadcast services ［J］.IEEE／ACM Transactions on Networking，2010，19（3）：869-878.

［10］WANG Y S， ZHANG Q Y.Anapproachonwireless broadcasting retransmission using network coding ［C］／／8th International Conference on Wireless Communications，NetworkingandMobileComputing （WiCOM）， September 21-23，2012，Shanghai，China.New Jersey：IEEE Press，2012：1-4.

［11］邵 鵬 飛，趙燕 偉，吳耀 輝，等. 多 播網(wǎng) 絡(luò) 中基 于機(jī) 會(huì) 網(wǎng)絡(luò) 編 碼改 進(jìn) 的 重 傳 方 法 ［J］. 電 信 科 學(xué) ，2015，31（4）：99-106. SHAO P F ，ZHAO Y W ，WU Y H ，et al.Animprovedretransmission approach based on opportunistic network coding in multicast networks［J］.Telecommunications Science，2015，31（4）：99-106.

［12］茍亮，張更 新，孫 偉，等. 無(wú) 線 網(wǎng)絡(luò) 中 基 于 機(jī)會(huì) 網(wǎng) 絡(luò)編 碼 的加權(quán) 廣 播 重 傳 ［J］. 電 子 與 信 息 學(xué) 報(bào) ，2014，36（3）：749-753. GOU L，ZHANG G X，SUN W，et al.Weighted broadcasting retransmission based on opportunistic network coding in wireless networks ［J］.Journal of Electronics&Information Technology，2014，36（3）：749-753.

［13］FAN P，ZHI C，WEI W，et al.Reliable relay assisted wireless multicast using network coding ［J］.IEEE Journal on Selected Areas in Communications，2009，27（5）：749-762.

［14］VIEN Q T，TRAN L N，HONG E K.Network coding-based retransmission for relay aided multisource multicast networks［J］. EURASIP Journal on Wireless Communications and Networking，2011（5）：1-10.

［15］方朝曦，李國(guó)勝，朱宇，等.一種基于聯(lián)合網(wǎng)絡(luò)編碼和信道解碼的 高 效率中繼技 術(shù)［J］. 電路與系統(tǒng) 學(xué) 報(bào)，2011，16（4）：120-124. FANG Z X，LI G S，ZHU Y，et al.A spectral efficient relaying scheme with joint network coding and channel decoding ［J］. Journal of Circuits and Systems，2011，16（4）：120-124.

［16］GOU L，ZHANG G X，SUN W，et al.WBRONC：efficient wireless broadcast retransmission based on opportunistic network coding［J］.Frequenz，2013，67（3／4）：117-125.

［17］盧 冀，肖 嵩，吳 成 柯. 一 種 基 于 機(jī) 會(huì) 式 網(wǎng) 絡(luò) 編 碼 的 高 效 廣 播重 傳 方 法 ［J］. 電 子 與 信 息 學(xué) 報(bào) ，2011，33（4）：858-863. LU J，XIAO S，WU C K.A high efficiency retransmission approach based on opportunistic network coding ［J］.Journal of Electronics&Information Technology，2011，33（4）：858-863.

A hash-neighborhood-search-network-coding based opportunistic relay retransmission approach

SHAO Pengfei1，2，ZHAO Yanwei3，F(xiàn)ANG Zhaoxi2
1.College of Computer Science&Technology，Zhejiang University of Technology，Hangzhou 310023，China 2.School of Electronic and Information Engineering，Zhejiang Wanli University，Ningbo 315100，China 3.College of Mechanical Engineering，Zhejiang University of Technology，Hangzhou 310023，China

In wireless multicast networks，it is rarely concerned that there may be certain receiving nodes which have better quality links both to the source node and to the other receiving nodes.A novel hash-neighborhoodsearch-network-coding based opportunistic relay retransmission approach was proposed.According to the packet reception status and channel quality，this novel approach dynamically selected the best suitable receiving node whose channel quality was better than the source node as a relay，then hash-neighborhood-search-network-coding strategy was used for the relay to retransmit other receiving nodes’ lost packets.Simulation results show that this novel approach can effectively reduce the number of retransmissions to improve the transmission efficiency with respect to the existing algorithms，especially when one or more of the receiving nodes are interfered and the quality of the channel between receiving nodes and source node continues to decline，this approach can achieve a high retransmission gain.

wireless multicast，network coding，opportunistic relaying，retransmission

s： The NationalNaturalScience Foundation of China （No.61379123，No.61401400）， Ningbo SocialDevelopment Foundation（No.2014C50006）

TN925

：A

10.11959／j.issn.1000-0801.2016090

邵鵬飛（1978-），男，浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士生，浙江萬(wàn)里學(xué)院電子信息學(xué)院副教授，主要研究方向?yàn)槲锫?lián)網(wǎng)中的可靠傳輸和信息融合。

趙燕偉（1959-），女，浙江工業(yè)大學(xué)機(jī)械工程學(xué)院博士生導(dǎo)師、教授，主要研究方向?yàn)橄冗M(jìn)制造技術(shù)、現(xiàn)代物流系統(tǒng)智能配送與優(yōu)化調(diào)度、網(wǎng)絡(luò)環(huán)境下的數(shù)字制造技術(shù)等。

方朝曦（1982-），男，博士，浙江萬(wàn)里學(xué)院電子信息學(xué)院副教授，主要研究方向?yàn)闊o(wú)線通信與網(wǎng)絡(luò)、物聯(lián)網(wǎng)工程。

2015-11-04；

2016-03-02

趙 燕 偉 ，zyw@zjut.edu.cn

國(guó) 家 自 然 科 學(xué) 基 金 資 助 項(xiàng) 目 （No.61379123，No.61401400）； 寧 波 市 社 會(huì) 發(fā) 展 基 金 資 助 項(xiàng) 目 （No.2014C50006）