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 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 transmissions.(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 Network 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.Assume 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 recover 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. 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 hypothetical 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 active capacity of cut is 1 + 2 2 1 2 3 3 1 1 2 1 2 3 m : 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.Construct 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 incoming 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: Construct 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. Soljanin, “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 original 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: Links 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 to 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 graph source nodesw ys tt yt ww zuws 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 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 and 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 Decomposition (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 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 Coding 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. nodes 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 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 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 subframe.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.14Distributed 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 Construction.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 code 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 energy consumption per packet transmission.Evaluate energy consumption per successfully delivered packet to destination nodes.III. Network Coding vs. Plain Routing (Contd)maximum improvement of network coding over routing:First Method: 26 %Scheduling Method A: 28 %Scheduling Method B: 22 %Scheduling Method C: 16 %17Addressed the problem of network coding in wireless networks.Constructed a network coding solution over predetermined network realizations.Presented distributed methods to derive conflict-free transmission schedules from network codes based on subtree network decomposition.Clearly the MAC aspect is not fully optimized. Contention-based protocols can be partially handled through Group TDMA.IV. Summary and Thoughts for Future WorkNext Problem: Network Coding for Wireless Queueing Networks.Previous assumption: Saturated queues (for both generated packets and relay traffic).New focus: Notion of delay or buffer overflow.Consider network coding decisions based on queue contents.18