Show simple item record

dc.contributor.authorLiau, Andrew
dc.contributor.otherQueen's University (Kingston, Ont.). Theses (Queen's University (Kingston, Ont.))en
dc.date2011-09-28 19:47:09.447en
dc.date2011-10-07 21:13:03.862en
dc.date.accessioned2011-10-11T14:16:05Z
dc.date.available2011-10-11T14:16:05Z
dc.date.issued2011-10-11
dc.identifier.urihttp://hdl.handle.net/1974/6833
dc.descriptionThesis (Master, Electrical & Computer Engineering) -- Queen's University, 2011-10-07 21:13:03.862en
dc.description.abstractNetwork coding (NC) is an optimal data dissemination technique where intermediate nodes linearly combine incoming packets. To recover a network-coded message, a sink must use a Gaussian elimination decoder, but this high-complexity decoder may not be acceptable in resource-constrained applications like sensor networks. A good alternative to Gaussian elimination is for the sink to apply the well-known belief propagation (BP) algorithm; however, the performance and complexity of BP decoding is dependent on the statistics of the linearly-combined packets. In this work, we propose two protocols that address this issue by applying fountain coding paradigms to network codes. For a two-source, single-relay, and single-sink network, named the Y-network, if the relay can network-code incoming packets while maintaining the key properties of the fountain code, then BP decoding can be applied efficiently to recover the original message. Particularly, the sink should see a Soliton-like degree distribution for efficient BP decoding. The first protocol, named Soliton-like rateless coding (SLRC), recognizes that certain encoded packets are essential for BP decoding to perform well. Therefore, the relay protects these important packets by immediately forwarding them to the sink. It can be shown analytically that the proposed scheme is resilient to nodes leaving the transmission session. Through simulations, the SLRC scheme is shown to perform better than buffer-and-forwarding, and the Distributed LT code. Although SLRC achieves good performance, the degree distribution seen by the sink is non-optimal and assumes that a large number of packets can be buffered, which may not always be possible. Extending SLRC, we propose the Improved Soliton-like Rateless Coding (ISLRC) protocol. Assuming a resource-constrained relay, the available resources at the relay are effciently utilized by performing distribution shaping; packets are intelligently linearly combined. The aggregate degree distribution for the worst case is derived and used in performing an asymptotic error analysis using an AND-OR tree analysis. Simulation results show that even under the worst case scenario of ISLRC, better performance can be achieved compared to SLRC and other existing schemes.en_US
dc.languageenen
dc.language.isoenen_US
dc.relation.ispartofseriesCanadian thesesen
dc.rightsThis publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.en
dc.subjectNetwork codingen_US
dc.subjectFountain codesen_US
dc.subjectLT Codesen_US
dc.titleLow-Complexity Soliton-like Network Coding for a Resource-Limited Relayen_US
dc.typeThesisen_US
dc.description.degreeMasteren
dc.contributor.supervisorYousefi, Shahramen
dc.contributor.supervisorKim, Il-Minen
dc.contributor.departmentElectrical and Computer Engineeringen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record