Crosslayer Design for Distributed MAC and Network Coding in 分布式MAC層和網(wǎng)絡(luò)編碼的跨層設(shè)計

1、Crosslayer Design for Distributed MAC and Network Coding in Wireless Ad Hoc NetworksYalin E. Sagduyu Anthony Ephremides University of Maryland at College Park2005 IEEE ISIT Adelaide, Australia1Background / MotivationNetwork coding was originally developed for wired networks.Objective: Extend network

2、 coding to operate in ad hoc wireless networks:Simultaneous multiple transmissions/receptions over different links (no interference).Throughput has been the main performance focus.(1) No simultaneous transmission and reception at any node. (2) Interference effects need for MAC.(3) Omnidirectional tr

3、ansmissions.(4) Slotted time.(5) Performance criteria: throughput, delay, energy-efficiency. Joint specification of MAC and network coding is necessary.Distributed solutions are needed for scalability.2OutlineI. Review of a Basic Method for Network Coding in a Wireless NetworkAddress both MAC and Ne

4、twork Coding. II. Improved Joint MAC and Network Coding MethodsIII. Sample ResultsIV. Future Work3Assume schedule-based interference-free MAC, i.e. conflict-free network realizations: Example of Wireless Network CodingSource s wishes to transmit packets of two flows (1&2) to destinations y and z.Ass

5、ume classical collision channel model:Channel Outcomes: Success, Idle, or CollisionLimited transmission/reception ranges with sharp boundariesSINR-based model is possible as well.Encoding : w computes b1 + b2 Decoding : 1. z computes b1 + (b1 + b2) to recover b2 2. y computes b2 + (b1 + b2) to recov

6、er b1stuwyzustwyzustwyzustwyzbit b1(k)b2(k+1)b1 (k)+b2 (k)b2(k)b2(k)b1(k)b1(k)b1 (k)+b2 (k)I. Review of a Basic Method for Network Coding 4Step 1: Predetermine conflict-free wireless network realizations. ustwyzssttuuwwyyzz The problem of optimal conflict-free transmission scheduling is NP-complete.

7、 Use a simple heuristic to construct conflict-free network realizations:Adequate Set of Network Realizations:One Network Realization: receiverustwyzutwtransmittersyzutwsyzI. Review of a Basic Method for Network Coding (Contd.) 5Step 2: Assign time fractions to network realizations.Construct a hypoth

8、etical wired network graph from the wireless network realizations: Choose m , m =1,2, to maximize average throughput per destination or minimize average energy cost per successfully delivered packet.A new definition of cut capacity is needed. link capacity = proportion of time during which link is a

9、ctive capacity of cut is1 + 2 2 1 2 3 3 1 1 2 1 2 3m : time fraction assigned to the m th network realizationI. Review of a Basic Method for Network Coding (Contd.) 6Set of wireless network realizations and hypothetical wired network graph have the same cut values and have the same maximum flows.Con

10、struct linear network codes for the hypothetical wired network using a polynomial-time algorithm.(e.g. S.Jaggi, P. A. Chou, K. Jain, “Low Complexity Algebraic Multicast Codes, ISIT 2003)Convert these wired network codes to wireless network codes such that: Nodes accumulate the packets generated or i

11、ncoming on different links over at most one schedule period.Nodes perform the same encoding and decoding operation as determined for the hypothetical wired network; but they encode or decode only during the network realizations for which they are activated as transmitters (or receivers). Step 3: Con

12、struct wireless network codes for the predetermined wireless network realizations.I. Review of a Basic Method for Network Coding (Contd.) 7Consider the problem of joint MAC (scheduling) and network coding. Single common network coding method (based on subtree decomposition). (C. Fragouli, E. Soljani

13、n, “Subtree Decomposition for Network Coding, ISIT 2004)Three different methods for the MAC part.Use the results of the common network coding method to construct conflict-free transmission schedules.II. Improved Joint MAC and Network Coding Methods8Step 1: Construct a dual line graph from the origin

14、al network graph. Subtree Decomposition of a Network GraphSource nodes in line graph: Links in original graph that are outgoing from a source node.Coding nodes in line graph: Links in original graph that are downstream and adjacent to more than one incoming link. Destination nodes in line graph: Lin

15、ks in original graph that are incoming to a destination.source nodesdestination nodesstuwyzOriginalGraph:w ys tt yt ww zu ws uu zDual Line Graph:coding nodessource nodedestination nodesdestination nodesII. Improved Joint MAC and Network Coding Methods (Contd.)9Step 2: Partition the dual line graph t

16、o subtrees such that 1. Each subtree contains exactly one source node OR exactly one coding node. 2. Any other node in dual graph belongs to the subtree that contains its first ancestral source or coding node.Step 3: Construct the subtree graph from the dual line graphsource nodesw ys tt yt ww zuws

17、uu zDual Line Graph:coding nodesT1T2T3T4Subtree Graph: Subtree Decomposition of a Network Graph, (Contd.) II. Improved Joint MAC and Network Coding Methods (Contd.)10Network Coding by Subtree DecompositionSource node in the original graph generates information vector x . y (e): symbol transmitted on

18、 link e in original graph (i.e. node e in dual line graph) y (e) = f (e) x T , where f (e) is code vector for node e in dual line graph.y (e) is constant for all e Ti . Consider f (Ti) as the code vector for subtree Ti . Successful decoding by destination nodes is assured if II. Improved Joint MAC a

19、nd Network Coding Methods (Contd.)(1) The code vector of any subtree is in the linear span of code vectors of parent subtrees.(2) The code vectors of any two subtrees that share a destination node or that are connected to a common child subtree are linearly independent.11Network Coding by Subtree De

20、composition (Contd.)Construct a special graph from subtree graph.Color the special graph and assign different network codes to subtrees that have been colored with different colors.T1T2T3T4Subtree Graph:T1T2T3T4Special Graph : additional linkIntroduce new links between nodes, if (1) these nodes are

21、connected to a common child node. or (2) the subtrees contain destination nodes (links in the original graph) such that these links lead to the same destination node (of original graph) Example: Code for T1 : 0,1 , Code for T2 : 1,0 , Codes for T3 and T4 : 1,1 II. Improved Joint MAC and Network Codi

22、ng Methods (Contd.)12Use the subtree decomposition of the network to construct conflict-free schedules.Scheduling Method A Divide each subframe into three time slots.Subtree 1Subtree 2Subframe 1Subframe 2depth 0depth 1depth 2depth 3Subtree: Nodes at depths 0,3, 1 and 2 are separately activated. node

23、s at depth levels 0, 3, 6, nodes at depth levels1, 4, 7, nodes at depth levels 2, 5, 8, FrameDivide nodes in eachsubtree into three disjoint node sets.slot 1slot 2slot 3II. Improved Joint MAC and Network Coding Methods (Contd.)Spatial Reuse: For a given subtree, all nodes at every third depth level

24、can be activated simultaneously. Choose the lengths of subframes (to either maximize throughput or minimize energy consumption per unit throughput).Divide time frame into subframes and match each subframe with exactly one subtree. 13Scheduling Methods B and CII. Improved Joint MAC and Network Coding

25、 Methods (Contd.)Different subtrees (i.e. subframes) may include nodes that can be simultaneously activated without any conflict. Refinement of Method A is needed:Method B: Determine network codes by assigning colors to subtrees.Combine all subtrees of the same color (i.e. code) into the same subfra

26、me.Subtrees of different colors may include nodes that can be simultaneously activated without any conflict.Refinement of Method B is needed: Method C: Better spatial reuse is possible through exhaustive search for nodes that can be activated also in other subframes without any conflict.14Distribute

27、d Implementation IssuesDistributed methods should only use local exchange of information among nodes.Questions: What amount of information is sufficient or necessary? 1. Coloring Conflict-free schedules among ordered nodes Can be implemented by well-known distributed heuristics. 2. Subtree Construct

28、ion.Issue: For the subtree graph, we need a distributed method for the identification of the subtrees.The existing methods are centralized and based on the availability of the global network information or global information exchange.If the identification of the subtrees is available, then network c

29、ode assignment can be implemented by well-known graph coloring heuristics. Still, methods for coloring the subtree nodes are needed.The aspect of distributed implementation is not finalized.15III. Network Coding vs. Plain RoutingConsider a square grid network with 9 nodes.A randomly selected source node chooses its multicast group of size m.Evaluate the total number of packets delivered to destination nodes per time slot. maximum improvement of network coding over routing:First Method: 28 %Scheduling Method A: 31 %Scheduling Method B: 24 %Scheduling Method C: 18 %16Consider unit en