Analyzing Random Network Coding With Differential Equations and Differential Inclusions

作者：Zhang Dan^*; Mandayam Narayan B

来源：IEEE Transactions on Information Theory, 2011, 57(12): 7932-7949.

DOI：10.1109/TIT.2011.2170107

• Capacity achievability
• concentration
• differential equation
• differential inclusion
• dynamical system
• random coupon selection
• random network coding

We develop a framework based on differential equations (DE) and differential inclusions (DI) for analyzing Random Network Coding (RNC) in an arbitrary wireless network. The DEDI framework serves as a powerful numerical and analytical tool to study RNC. For demonstration, we first build a system of DE's with this framework, under the fluid approximation, to model the means of the rank evolution processes. By converting this system to DI's and explicitly solving them, we show that the average multicast throughput is equal to the min-cut bound. We then turn to the precise system of DE's regarding the means and variances of the rank evolution processes. By analyzing this system, we show that the rank evolution processes asymptotically concentrate to the solution of the DI's obtained previously. From this result, it immediately follows that the min-cut bound can be achieved as the number of source packets becomes large. We demonstrate the numerical accuracy and flexibility in performance analysis enabled by the DEDI framework via illustrative examples of networks with multiple multicast sessions, complex topology and correlated reception. We also briefly discuss its application in MAC and PHY adaptation and the extension to Random Coupon Selection.

• 出版日期2011-12
• 单位rutgers