On Vector Random Linear Network Coding in Wireless Broadcasts
Compared with scalar linear network coding (LNC) formulated over the finite field GF(<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mn>2</mn><mi>L</mi></msup></semantics&...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/6/559 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849472045994213376 |
|---|---|
| author | Rina Su Chengji Zhao Qifu Sun Zhongshan Zhang |
| author_facet | Rina Su Chengji Zhao Qifu Sun Zhongshan Zhang |
| author_sort | Rina Su |
| collection | DOAJ |
| description | Compared with scalar linear network coding (LNC) formulated over the finite field GF(<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mn>2</mn><mi>L</mi></msup></semantics></math></inline-formula>), vector LNC offers enhanced flexibility in the code design by enabling linear operations over the vector space <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>GF</mi><msup><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow><mi>L</mi></msup></mrow></semantics></math></inline-formula> and demonstrates a number of advantages over scalar LNC. While random LNC (RLNC) has shown significant potential to improve the completion delay performance in wireless broadcasts, most prior studies focus on scalar RLNC. In particular, it is well known that, with increasing <i>L</i>, primitive scalar RLNC over GF(<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mn>2</mn><mi>L</mi></msup></semantics></math></inline-formula>) asymptotically achieves the optimal completion delay. However, the completion delay performance of primitive vector RLNC remains unexplored. This work aims to fill in this blank. We derive closed-form expressions for the probability distribution and the expected value of both the completion delay at a single receiver and the system completion delay. We further unveil a fundamental limitation that is different from scalar RLNC: even for large enough <i>L</i>, primitive vector RLNC over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>GF</mi><msup><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow><mi>L</mi></msup></mrow></semantics></math></inline-formula> inherently fails to reach optimal completion delay. In spite of this, the gap between the expected completion delay at a receiver and the optimal one is shown to be a constant smaller than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>0.714</mn></mrow></semantics></math></inline-formula>, which implies that the expected completion delay normalized by the number <i>P</i> of original packets is asymptotically optimal with increasing <i>P</i>. We also validate our theoretical characterization through numerical simulations. Our theoretical characterization establishes primitive vector RLNC as a performance baseline for the future design of practical vector RLNC schemes with different design goals. |
| format | Article |
| id | doaj-art-adb4826c809a4efd838bd2eeb4a9f540 |
| institution | Kabale University |
| issn | 1099-4300 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj-art-adb4826c809a4efd838bd2eeb4a9f5402025-08-20T03:24:37ZengMDPI AGEntropy1099-43002025-05-0127655910.3390/e27060559On Vector Random Linear Network Coding in Wireless BroadcastsRina Su0Chengji Zhao1Qifu Sun2Zhongshan Zhang3School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing 100081, ChinaSchool of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, ChinaSchool of Computer and Communication Engineering, University of Science and Technology Beijing, Beijing 100083, ChinaSchool of Cyberspace Science and Technology, Beijing Institute of Technology (ZhuHai), Zhuhai 519088, ChinaCompared with scalar linear network coding (LNC) formulated over the finite field GF(<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mn>2</mn><mi>L</mi></msup></semantics></math></inline-formula>), vector LNC offers enhanced flexibility in the code design by enabling linear operations over the vector space <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>GF</mi><msup><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow><mi>L</mi></msup></mrow></semantics></math></inline-formula> and demonstrates a number of advantages over scalar LNC. While random LNC (RLNC) has shown significant potential to improve the completion delay performance in wireless broadcasts, most prior studies focus on scalar RLNC. In particular, it is well known that, with increasing <i>L</i>, primitive scalar RLNC over GF(<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mn>2</mn><mi>L</mi></msup></semantics></math></inline-formula>) asymptotically achieves the optimal completion delay. However, the completion delay performance of primitive vector RLNC remains unexplored. This work aims to fill in this blank. We derive closed-form expressions for the probability distribution and the expected value of both the completion delay at a single receiver and the system completion delay. We further unveil a fundamental limitation that is different from scalar RLNC: even for large enough <i>L</i>, primitive vector RLNC over <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>GF</mi><msup><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow><mi>L</mi></msup></mrow></semantics></math></inline-formula> inherently fails to reach optimal completion delay. In spite of this, the gap between the expected completion delay at a receiver and the optimal one is shown to be a constant smaller than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>0.714</mn></mrow></semantics></math></inline-formula>, which implies that the expected completion delay normalized by the number <i>P</i> of original packets is asymptotically optimal with increasing <i>P</i>. We also validate our theoretical characterization through numerical simulations. Our theoretical characterization establishes primitive vector RLNC as a performance baseline for the future design of practical vector RLNC schemes with different design goals.https://www.mdpi.com/1099-4300/27/6/559random linear network coding (RLNC)vector linear network coding (VLNC)completion delaywireless broadcast |
| spellingShingle | Rina Su Chengji Zhao Qifu Sun Zhongshan Zhang On Vector Random Linear Network Coding in Wireless Broadcasts Entropy random linear network coding (RLNC) vector linear network coding (VLNC) completion delay wireless broadcast |
| title | On Vector Random Linear Network Coding in Wireless Broadcasts |
| title_full | On Vector Random Linear Network Coding in Wireless Broadcasts |
| title_fullStr | On Vector Random Linear Network Coding in Wireless Broadcasts |
| title_full_unstemmed | On Vector Random Linear Network Coding in Wireless Broadcasts |
| title_short | On Vector Random Linear Network Coding in Wireless Broadcasts |
| title_sort | on vector random linear network coding in wireless broadcasts |
| topic | random linear network coding (RLNC) vector linear network coding (VLNC) completion delay wireless broadcast |
| url | https://www.mdpi.com/1099-4300/27/6/559 |
| work_keys_str_mv | AT rinasu onvectorrandomlinearnetworkcodinginwirelessbroadcasts AT chengjizhao onvectorrandomlinearnetworkcodinginwirelessbroadcasts AT qifusun onvectorrandomlinearnetworkcodinginwirelessbroadcasts AT zhongshanzhang onvectorrandomlinearnetworkcodinginwirelessbroadcasts |