Open Access Open Access  Restricted Access Subscription Access

Wireless Networks Using Matroid along with Network Coding

Purnendu Shekhar Pandey,
Neetesh Purohit,
Shekhar Verma,


Network coding has a vast impact on the throughput of a network. It not only combines the packet to improve throughput but it makes it more robust from errors. A fundamental problem for applying network coding is to find the number of nodes that can be treated as network coding nodes. It is found that application of network coding to every node within network results in more delay and increases the computational complexity which ultimately results in huge congestion and packet loss. Whereas selective network coding node selection decreases packet replication and increases innovative flow rate within network. To overcome this node selection problem for dynamic changing network, we have applied the concept of Matroid to construct network and form various spanning trees out of that matroidal network. In this process, subsequently Greedy algorithm for matroid is applied to find the most suitable spanning tree with minimum weight. Hence forth, Priority based selection scheme is used to prioritize the nodes within the network and subsequently nodes having highest priority will perform network coding. Lastly, we have applied an algorithm to select the best spanning tree with the help of Laplacian Matrix and all these schemes put together are named as Rule Based Selective Scheme. Thus, priority node selection and dynamic switching of spanning trees and selected NC nodes, in case of congestion, makes this rule based selective scheme more appropriate for real scenarios whereas centrality based scheme and random selection scheme do not follow this approach. The Comparative results have shown a clear indication that fi nding and applying network coding to selected number of nodes in accordance with our algorithm produces better throughput, reduces decoding delay and dynamic switching in case of congestion makes it more effi cient as compared to other mentioned schemes.


Matroid; Network coding; Coding gain; XOR; Decoding delay

Citation Format:
Purnendu Shekhar Pandey, Neetesh Purohit, Shekhar Verma, "Wireless Networks Using Matroid along with Network Coding," Journal of Internet Technology, vol. 18, no. 4 , pp. 775-786, Jul. 2017.

Full Text:



  • There are currently no refbacks.

Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Library and Information Center, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd. Shoufeng, Hualien 97401, Taiwan, R.O.C.
Tel: +886-3-931-7017  E-mail: