上海交通大学：Network Coding for Wireless Networks（PPT讲稿）

Network Coding for Wireless Networks Wireless Communication Project by Group 2 Shang Shang Ma Rong Yang Yang Wang Chen 5+/1

Network Coding for Wireless Networks Wireless Communication Project by Group 2 1

Network Coding for Wireless Networks INTRODUCTION 2 COPE DESCRIPTION 3> COPE IMPLEMENTATION 4>ANALOG NETWORK CODING

Network Coding for Wireless Networks 1 INTRODUCTION 2 COPE DESCRIPTION 3 COPE IMPLEMENTATION 4 ANALOG NETWORK CODING 2

Introduction Why? Network What? Coding Definitions

Network What? Coding Why? Definitions Introduction 3

Definitions 3 Max-flow Min-cut Unicast Throug h Theory Multicast put

1 Max-flow Min-cut Theory 2 Unicast, Multicast 3 Through￾put Definitions 4

Max-Flow Min-Cut Theorem (From Wiki) The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks The maximal amount of flow is equal to the capacity of a minimal cut The maximum flow in a network is dictated by its bottleneck [1]S.-YR Li, R. W. Yeung and N Cai, Linear network Coding, IEEE Trans

Max-Flow Min-Cut Theorem • (From Wiki) The max-flow min-cut theorem is a statement in optimization theory about maximal flows in flow networks • The maximal amount of flow is equal to the capacity of a minimal cut. • The maximum flow in a network is dictated by its bottleneck. [1] S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network Coding”, IEEE Trans. 5

Graph Graph G(V, E): consists of a set V of vertices and a set E of edges Vconsists of sources sinks and other nodes A member e(u,v) of E has a capacity c(u, vto send information from u to y

Graph • Graph G(V,E): consists of a set and a set – V consists of sources, sinks, and other nodes – A member e(u,v) of E has a to send information from u to v A D S B C T V of vertices E of edges. S A B D C T 3 3 3 3 2 2 2 4 capacity c(u,v) 6

Min-Cuts and max-Flows Cuts: Partition of vertices into two sets Size of a Cut = Total Capacity Crossing the Cut Min -Cut: Minimum size of cuts 5 Max-Flows from s to t Min -Cut= Max-Flow 3 A 2 2 D 2 C

Min-Cuts and Max-Flows • Cuts: Partition of vertices into two sets • Size of a Cut = Total Capacity Crossing the Cut • Min-Cut: Minimum size of Cuts = 5 • Max-Flows from S to T • Min-Cut = Max-Flow S A B D C T 3 3 3 3 2 2 2 S 4 A D 3 3 3 2 2 B C T 3 3 2 2 4 3 2 3 2 3 2 1 7

Unicast Multicast Broadcast Broadcast Multicast communicat Unicast communicat ion Is one communicat ion is one to-a∥ ion is one- to-many. to-one

Unicast | Multicast | Broadcast Multicast Broadcast Unicast Unicast communicat ion is one￾to-one. Multicast communicat ion is one￾to-many. Broadcast communicat ion is one￾to-all. 8

Throughput The amount of data transferred from one place to another or processed in a specified amount of time Data transfer rates for disk drives and networks are measured in terms of throughput. Typically, throughputs are measured in kbps, Mbps and Gbps

Throughput • The amount of data transferred from one place to another or processed in a specified amount of time. • Data transfer rates for disk drives and networks are measured in terms of throughput. Typically, throughputs are measured in kbps, Mbps and Gbps. 9

Wire vs wireless Wire VS Wireless WIRE WIRELESS v An edge between two nodes √ The channel of one means that the two nodes are particular edge is actually physically connected Network Modeling shared by other neighboring edge v Multicast communication is studied while network coding v Unicast communication is of multiple unicast flows remains Traffic Pattern the dominate traffic pattern a largely unknown territory v Traffic rates are varies over Y The traffic rate(or distribution) time rather than constant is predetermined and Traffic Rate do not change

Wire vs Wireless ✓An edge between two nodes means that the two nodes are physically connected. ✓Multicast communication is studied while network coding of multiple unicast flows remains a largely unknown territory. ✓The traffic rate (or distribution) is predetermined and do not change. Wire vs Wireless ✓The channel of one particular edge is actually shared by other neighboring edge. ✓ Unicast communication is the dominate traffic pattern. ✓Traffic rates are varies over time rather than constant. Network Modeling Traffic Pattern Traffic Rate WIRE WIRELESS 10