Abstract:
This invention proposes unique methods and apparatus for networking low cost low energy sensor nodes. The invention focuses on efficient Media Access Control (MAC) schemes to provide differentiated Quality of Service (QoS) to the sensor nodes in single-hop wireless and wired networks where the source nodes do not have a receiver module. Hence they can only transmit data to a sink but cannot receive any control signals, like an ACK or NAK, from any other node. None of the existing schemes like polling or scheduled transmissions, CSMA or ARQ is thus effective in this type of networks. The proposed scheme provides QoS to the nodes using distributed control by allowing them to transmit each packet an optimal number of times within a given interval.

Description:
RELATED APPLICATIONS 
       [0001]    This application claims priority to Provisional Patent Application, Ser. No. 60/920,716, filed Mar. 29, 2007. 
     
    
     FIELD OF THE INVENTION 
       [0002]    This invention is in the field of communications in sensor networks, including wireless and RFID network, and relates to the application of unique methods and apparatus for Media Access Control (MAC) to reduce the hardware cost and to provide differentiated Quality of Service (QoS) to the sensor nodes. 
       BACKGROUND OF THE INVENTION 
       [0003]    Present day wireless/wired sensor networks and RFID-based passive networks are employed for a wide range of applications such as Smart Home, Green House Monitoring, Medical Monitoring, Intra-Vehicular Networks, Intelligent Transportation, and Inventory Management Systems. These networks typically consist of one (or a few) sink node(s) and a large number of data source nodes, each of which generates data and transmits it to the sink node(s) through a common communication medium (e.g., wireless channel, wired medium). In order to enable large scale deployments of such networks it is desirable that each source node be a low complexity, low cost device that can provide the performance of existing devices. 
         [0004]    In general, such network deployments use devices that have both transmitting and receiving capability. However, in most applications we notice that the devices generally collect data and transmit it to a sink node. There is very minimal communication from the sink node to the data source nodes. The receiver circuitry adds to the cost of the device and also consumes a significant amount of power during operation. Thus by using nodes that have only transmitters and no receivers, the device cost and the entire infrastructure cost can be considerably reduced. 
         [0005]    An important aspect of deploying such networks is to choose a suitable Media Access Control (MAC) scheme for accessing the shared communication channel (eg. wireless medium). It is also important that the MAC scheme is able to provide differentiated Quality of Service (QoS) to the nodes. For example, in an intra-vehicular network, the data generated by a sensor node that senses the status of the brakes is more important than that generated by a sensor node sensing the status of the tail lights. Hence the data transmitted by the brake sensor must be given priority over the tail light sensor. 
         [0006]    Another important consideration is the lifetime of the network. Since in most cases the nodes are battery powered, it is important that they are very energy efficient in order that the lifetime and hence the cost of operation of the network is maximized. The MAC scheme plays a significant role in conserving energy as it controls the physical layer (eg. radio module) which is the major consumer of power in any network device. 
         [0007]    Existing MAC protocols can be largely categorized into polling based, scheduled transmissions, Carrier Sense Multiple Access (CSMA), Automatic Repeat reQuest (ARQ) based schemes. However, all these techniques require that all nodes have the capability to receive. This is due to the fact that all the schemes need to provide some form of feedback to the nodes in order to guarantee differentiated Quality of Service. But, for the networks we consider in this work, the nodes do not have the capability to receive. Hence it is impossible to use the existing MAC schemes. 
         [0008]    The invention addresses this problem by eliminating the need for feedback mechanisms. The MAC scheme developed in this work is capable of providing differentiated quality of service to the nodes and also ensures an energy efficient design. 
       SUMMARY OF INVENTION 
       [0009]    The following paragraphs describe the methods used for media access control and differentiated QoS in low cost and energy efficient sensor or RFID networks, in which, the sensor nodes are only capable of transmitting data and cannot receive any signals. 
         [0010]    The primary approach is to allow each node to transmit each of its data frames multiple times, thus increasing the probability of delivery. The fact that data frame transmission duration is relatively small when compared to the data generation rate makes retransmissions of data frames before the generation of the next data frame meaningful and forms the basis of the invented method. In addition, if a frame cannot be successfully delivered within a data generation interval, T units of time, the data frame is simply discarded. This ensures that the latest data frame has a greater chance of being successfully delivered and also bounds the latency. Accordingly, the latency is randomly distributed in the interval (0, T) and is bounded by T. 
         [0011]    However, the problem posed by this approach is that, if all the nodes follow a greedy approach and try to transmit their data a large number of times it will result in a large number of collisions and the number of successful transmissions will be very small (see Diagram  2 ). Thus the maximum delivery probability that can be achieved by each individual node will eventually be decreased. 
         [0012]    Hence, the optimal number of retransmission that each node should attempt for each of its data frames is determined in the invented method, so that all the nodes in the network achieve their required QoS in terms of data delivery probability. 
         [0013]    Specifically, the sensor nodes are classified into multiple QoS classes according to their data generation rate and required QoS in terms of frame delivery probability. Suppose that there are m QoS classes, {Q 1 , . . . , Q m }, and each class contains (n 1 , . . . , n m ) nodes respectively. Each node in Q i  requires a minimum frame delivery probability of p i  (1≦i≦m). The packet arrival rates of the nodes in each class are {T 1 , . . . , T m } respectively. Given the classified nodes and QoS requirement, the optimal number of retransmissions, x i , for each Q i  is determined using NLP (Non-Linear Programming) or NLIP (Non-Linear Integer Programming), such that, if every node in a Q i  transmits x i  times in every T i  units of time, it can achieve a delivery probability of at least pi. 
         [0014]    Further, we define three optimization problems to improve applicability of the invention to the networks under consideration. First, in order to be energy efficient, source nodes need to transmit as little as possible. Based on this consideration, we can find the minimum value of the number of retransmissions that achieves the required delivery probabilities of the nodes. Second, in certain conditions the main criteria might be the delivery probability of the high priority nodes. They might require the highest possible delivery probability that can be achieved for the given network parameters. Third, in some applications of sensor or RFID networks, it may be desirable to have as many nodes as possible in the highest priority class. 
         [0015]    Based on the above discussion, the optimization criteria can be summarized as
   1. Minimize the total network traffic. Alternatively, minimize x i  for every Q i .   2. Maximize the delivery probability of the nodes in the highest priority class.   3. Maximize the number of nodes that can be accommodated in the highest priority class   
 
         [0019]    The invented method is applicable to the case where the nodes can transmit on different channels using, for example, CDMA. Unlike most of the existing work on multi-channel (CDMA) wireless networks, we consider interference among the packets sent on different channels when analyzing the packet delivery probability. Multi-packet detection in a CDMA environment is a challenging design issue and the methods of analyzing packet error rate taking into consideration the multiple-access interference is largely an open problem. We develop a general model that attempts to capture the effects of Multiple Access Interference (MAI) in the analysis of the packet error probability. 
     
    
     
       DESCRIPTION OF DRAWINGS 
         [0020]    Drawing  1  depicts a typical network setup and shows an abstraction of the components contained in each sensor node. 
           [0021]    Drawing  2   a  depicts the scenario when an RFID reader transmits a stimulus pulse which energizes the RFID tags and causes them to transmit data. 
           [0022]    Drawing  2   b  depicts the scenario where, if all the RFID tags respond as soon as they receive the stimulus pulse, the resulting transmissions will collide and the RFID reader device would not be able to decode any useful information. 
           [0023]    Drawing  3  depicts the random retransmissions of each node within each interval ‘T’ based on its own local clock. There is no global time reference in the network however the figure shows it to highlight the fact that there is no global time synchronization between the nodes. 
           [0024]    Drawing  4  depicts the transmissions by different nodes that belong to different priority classes. It shows that a node having a higher priority will transmit a higher number of times within the said interval than a node having a lower priority. 
           [0025]    Drawing  5  shows a general scheme to allocate different channels to nodes requiring different priorities. The nodes in each priority class are allocated one of two channels. The ratio in which the nodes in each priority class are divided among the two communication channels is predetermined. 
           [0026]    Drawing  6  depicts the case where multiple communication channels are used. The figure shows the case where the transmissions of different codes overlap. However, they do not cause errors in each other as they use different codes (different communication channels). 
           [0027]    Drawing  7  depicts the condition under which the transmissions using different communications channels (codes) can cause errors in each other by interfering with each other. The figure shows the condition when, if more than three transmissions using the other channel overlap with a transmission of a particular channel, the resulting interference causes errors in the current transmission. 
       
    
    
     DETAILED DESCRIPTION OF INVENTION 
       [0028]    We consider a network architecture in which the data source nodes generate information and transmit it periodically to a central sink node as shown in Diagram  1 . The set of n (&gt;1) nodes are partitioned into m QoS classes, {Q 1 , . . . Q m }, with each class containing (n 1 , . . . , n m ) nodes respectively. The packet arrival rates of the nodes in each class are {T 1 , . . . , T m } respectively and the frame transmission duration, t f , of all the nodes is assumed to be the same. Each node in Q i  requires a minimum frame delivery probability of p i  (1&lt;=i&lt;=m). For simplicity, the groups are ordered such that, if i&lt;j, then p i ≧p j  and T i ≦T j . The core problem is to find the optimal number of retransmissions x i  for each Q i , such that, if every node in Q i  transmits x i  times in every T i  units of time, as shown in Diagram  3 , it can achieve a delivery probability of at least p i .
   1. The Case Where All the Nodes in the Network Require the Same Delivery Probability (p 1 =p 2 = . . . =p m ) and Only a Single Communication Channel is Used   
 
         [0030]    In this case, all the nodes in the network need to achieve the same delivery probability. It is assumed that the source nodes generate data at a constant rate of one frame every ‘T’ units of time and the transmission time for each frame is much smaller than the inter-frame duration. Under this assumption the frame arrival rate can be modeled as a Poisson process. The number of nodes in the network is denoted by ‘n’ and the number of transmissions by each node in every interval ‘T’ is denoted by ‘x’. 
         [0031]    Suppose that node i transmits a frame at time t 0  and the duration of the transmission is t f . Assuming the signal propagation delay is negligible, none of the other n−1 nodes should transmit during the interval [t 0 −t f , t 0 +t f ] in order that the frame does not collide and hence is successfully received by the destination node. 
         [0032]    The frame arrival rate or the rate at which the source nodes generate the data can be modeled as a Poisson process and the probability that ‘k’ frames are transmitted in an interval ‘t’ is given by 
         [0000]    
       
         
           
             
               P 
                
               
                 [ 
                 
                   
                     n 
                     ′ 
                   
                   = 
                   k 
                 
                 ] 
               
             
             = 
             
               
                 
                    
                   - 
                 
                 
                   
                     - 
                     λ 
                   
                    
                   
                       
                   
                    
                   t 
                 
               
                
               
                 
                   
                     ( 
                     
                       λ 
                        
                       
                           
                       
                        
                       t 
                     
                     ) 
                   
                   k 
                 
                 
                   k 
                   ! 
                 
               
             
           
         
       
     
         [0033]    The probability that the frame transmitted by node i does not collide is the same as the probability that zero frames were transmitted by the other n−1 nodes in an interval 2t f . This is given by 
         [0000]    
       
      
       D 
       nc 
       =e 
       −2λt 
       
         f 
       
      
     
         [0000]    Here λ is the rate of background traffic generated by the other n−1 nodes and is given by 
         [0000]    
       
         
           
             λ 
             = 
             
               
                 
                   ( 
                   
                     n 
                     - 
                     1 
                   
                   ) 
                 
                  
                 x 
               
               T 
             
           
         
       
     
         [0034]    The above discussion presents the probability that a frame transmitted by node i is successfully received by the receiver. However, node i transmits ‘x’ copies of the frame at random instants in every time interval ‘T’. Hence the actual parameter of interest will be the probability that at least one of these ‘x’ copies is successfully received at the destination, which is defined as the delivery probability or QoS requirement of the node. 
         [0035]    The delivery probability of each frame is given by 
         [0000]    
       
         
           
             
               P 
                
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               1 
               - 
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   x 
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     1 
                     - 
                     
                       D 
                       nc 
                     
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    which results in 
         [0000]    
       
         
           
             
               P 
                
               
                 ( 
                 x 
                 ) 
               
             
             = 
             
               1 
               - 
               
                 
                   ( 
                   
                     1 
                     - 
                     
                        
                       
                         
                           
                             - 
                             2 
                           
                            
                           
                               
                           
                            
                           
                             x 
                              
                             
                               ( 
                               
                                 n 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                            
                           
                             t 
                             f 
                           
                         
                         T 
                       
                     
                   
                   ) 
                 
                 x 
               
             
           
         
       
     
         [0036]    This expresses the delivery probability as a function of the number of transmissions attempted by each node in the interval ‘T’. Now, we can maximize the delivery probability with respect to the number of transmission. The delivery probability is maximized when 
         [0000]    
       
         
           
             x 
             = 
             
               
                 ln 
                  
                 
                     
                 
                  
                 2 
               
               R 
             
           
         
       
     
         [0000]    where, 
         [0000]    
       
         
           
             R 
             = 
             
               
                 2 
                  
                 
                     
                 
                  
                 
                   
                     t 
                     f 
                   
                    
                   
                     ( 
                     
                       n 
                       - 
                       1 
                     
                     ) 
                   
                 
               
               T 
             
           
         
       
     
         [0000]    The maximum delivery probability that can be achieved is given by 
         [0000]    
       
         
           
             
               P 
               max 
             
             = 
             
               1 
               - 
               
                 
                   ( 
                   
                     1 
                     - 
                     
                        
                       
                         
                           - 
                           ln 
                         
                          
                         
                             
                         
                          
                         2 
                       
                     
                   
                   ) 
                 
                 
                   
                     ln 
                      
                     
                         
                     
                      
                     2 
                   
                   R 
                 
               
             
           
         
       
     
         [0037]    The above result gives a relationship between the maximum delivery probability that can be achieved, the number of transmission attempts that each node makes in every interval ‘T’ and the number of nodes. By fixing any one variable we can design a network that is optimum in the other two variables. For example, if we fix the delivery probability requirement we can optimize the network to either have maximum number of nodes (maximize the number of users) or a minimum number of transmission attempts (minimize the energy consumption).
   2. The Case Where Nodes in the Network Require Different Delivery Probabilities and Only a Single Communication Channel is Used   
 
         [0039]    Proceeding with the analysis similar to that of the single QoS class case, the probability that a transmission from a node in Q i  does not collide with transmissions from any other node in the network is given by 
         [0000]    
       
      
       D 
       i 
       nc 
       =e 
       −2λ 
       
         i 
       
       t 
       
         f 
       
      
     
         [0040]    Here the rate of the background traffic λ i  is traffic generated per unit time by all other nodes in group i as well as all the nodes in the other groups and is given by 
         [0000]    
       
         
           
             
               λ 
               i 
             
             = 
             
               
                 
                   
                     n 
                     1 
                   
                    
                   
                     x 
                     1 
                   
                 
                 + 
                 
                   
                     n 
                     2 
                   
                    
                   
                     x 
                     2 
                   
                 
                 + 
                 ⋯ 
                 + 
                 
                   
                     n 
                     m 
                   
                    
                   
                     x 
                     m 
                   
                 
                 - 
                 
                   x 
                   i 
                 
               
               T 
             
           
         
       
     
         [0000]    The frame delivery probability achieved by a node in Q i  can then be expressed as 
         [0000]        P   i ( x   i )=1−(1− e   −2λ     i     t     f   ) x     i     
         [0041]    In this case it is difficult to obtain a closed form expression for the maximum value of P i (x i ), since it depends on all x i , iε{1, . . . , m}. Hence we formulate optimization problems based on the required network characteristics and solve for the different variables using known numerical methods. 
         [0042]    We can optimize the above solution such that the number of transmission attempts made by each node is minimized hence minimizing the total network traffic. This will also result in higher energy efficiency of the nodes. The basic problem formulation is described as follows. 
         [0043]    Given number of nodes in each group {n 1 , . . . , n m } and the minimum delivery probability requirements of the groups {p 1 , . . . , p m } we are required to find number of transmission to be attempted by each node in G i  {x 1 , . . . , x m } such that 
         [0000]    
       
         
           
             
               ∑ 
               
                 i 
                 = 
                 1 
               
               m 
             
              
             
                 
             
              
             
               
                 n 
                 i 
               
               × 
               
                 x 
                 i 
               
             
           
         
       
     
         [0000]    is minimized, subject to 
         [0000]      1− e   −2λ     j     t     f   −(1− p   j ) 1/x     j   ≦0 j=1 . . . m 
         [0000]    and 
         [0000]      1≦ x   j   ≦T/t   f  j=1 . . . m 
         [0044]    Alternatively, we can choose to maximize the delivery probability of the highest priority class (try to achieve as much as possible beyond the minimum required delivery probability) given {n 1 , . . . , n m } and the minimum delivery probability requirement of the other groups {p 2 , . . . p m } find the maximum achievable P 1 (x 1 ) subject to the above mentioned constraints. 
         [0045]    Thirdly, we can choose to maximize the number of nodes that can be accommodated in the highest priority class n 1  given the number of nodes in the other groups {n 2 , . . . , n m } and {p 1 , . . . , p m }. 
         [0046]    One of the methods we can use (and have used) to achieve the above optimization goals is to formulate each and every optimization problem above as an NLP (Nonlinear programming, assuming x i  is a real number) or NLIP (Nonlinear Integer programming, assuming x i  is an integer) problem. The NLP and the NLIP problems can be solved by using existing software packages (e.g., Lingo and Matlab Optimization toolbox) or a custom developed program which implements a Brute force algorithm to obtain the solutions.
   3. The Case Where Nodes in the Network Require Different Delivery Probabilities and Multiple Communication Channels are Used   
 
         [0048]    We develop mathematical expressions for the delivery probability considering the use of CDMA. For ease of presentation of the ideas we first consider a specific case when there are two QoS classes Q 1  and Q 2  containing n 1  and n 2  nodes and requiring minimum delivery probability p 1  and p 2  (p 1 &gt;p 2 ) respectively. Each node can be assigned any one of two codes. 
         [0049]    More specifically, we divide the nodes in class Q 1  into two sub-classes Q 11  and Q 12  which contain n 11  and n 12  nodes respectively, such that, n 11 +n 12 =n 1 . The nodes in Q 11  are assigned code C 1  and those in Q 12  are assigned code C 2 . Note that both the subgroups Q 11  and Q 12  require a minimum delivery probability of p 1 . Similarly the nodes in class Q 2  are divided into two subgroups Q 21  and Q 22 . Note that the subgroups Q 11 , Q 21  and Q 12 , Q 22  form two multiple QoS class systems. 
         [0050]    However, they are not independent as the transmissions generated by one system (using C 1 ) interfere with and hence cause errors in the transmissions of the other system (using C 2 ). Diagram  5  and Diagram  6  show the transmissions of the nodes under such conditions. Now, we attempt to develop analytic formulae for the delivery probability of the nodes for the general case of ‘m’ QoS classes. Assume that a set of n nodes are partitioned into m QoS classes, {Q1, . . . , Q m }, with each class containing {n 1 , . . . , n m } nodes respectively. As discussed above these classes are further divided into sub-classes {(Q 11 ,Q 12 ), . . . , (Q m1 ;Q m2 )} such that the nodes in classes Q i1  use code C 1  and the nodes in classes Q i2  use code C 2 . We restrict this discussion to the use of only two codes in order to facilitate the presentation. 
         [0051]    Again, note that the subgroups {Q 11 , . . . , Q m1 } and {Q 12 , . . . , Q m2 } form two multiple QoS class system. The background network traffic for a node in Q ij  is defined as the traffic generated by all other nodes using the same code as the node and its rate is given by 
         [0000]    
       
         
           
             
               λ 
               ij 
             
             = 
             
               
                 
                   
                     n 
                     
                       1 
                        
                       
                           
                       
                        
                       j 
                     
                   
                    
                   
                     x 
                     
                       1 
                        
                       
                           
                       
                        
                       j 
                     
                   
                 
                 
                   T 
                   
                     1 
                      
                     
                         
                     
                      
                     j 
                   
                 
               
               + 
               
                 
                   
                     n 
                     
                       2 
                        
                       
                           
                       
                        
                       j 
                     
                   
                    
                   
                     x 
                     
                       2 
                        
                       
                           
                       
                        
                       j 
                     
                   
                 
                 
                   T 
                   
                     2 
                      
                     
                         
                     
                      
                     j 
                   
                 
               
               + 
               ⋯ 
               + 
               
                 
                   
                     n 
                     mj 
                   
                    
                   
                     x 
                     mj 
                   
                 
                 
                   T 
                   mj 
                 
               
               - 
               
                 
                   x 
                   ij 
                 
                 
                   T 
                   ij 
                 
               
             
           
         
       
       
         
           
             
               
                 where 
                  
                 
                     
                 
                  
                 i 
               
               ∈ 
               
                 
                   { 
                   
                     1 
                     , 
                     … 
                      
                     
                         
                     
                     , 
                     m 
                   
                   } 
                 
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 j 
               
               ∈ 
               
                 
                   { 
                   
                     1 
                     , 
                     2 
                   
                   } 
                 
                 . 
               
             
              
             
                 
             
           
         
       
     
         [0052]    The interfering traffic is defined as the traffic generated by all the nodes using a different code and its rate is given by 
         [0000]    
       
         
           
             
               λ 
               ij 
               ′ 
             
             = 
             
               
                 
                   
                     n 
                     
                       1 
                        
                       
                           
                       
                        
                       
                         j 
                         ′ 
                       
                     
                   
                    
                   
                     x 
                     
                       1 
                        
                       
                           
                       
                        
                       
                         j 
                         ′ 
                       
                     
                   
                 
                 
                   T 
                   
                     1 
                      
                     
                         
                     
                      
                     
                       j 
                       ′ 
                     
                   
                 
               
               + 
               
                 
                   
                     n 
                     
                       2 
                        
                       
                           
                       
                        
                       
                         j 
                         ′ 
                       
                     
                   
                    
                   
                     x 
                     
                       2 
                        
                       
                           
                       
                        
                       
                         j 
                         ′ 
                       
                     
                   
                 
                 
                   T 
                   
                     2 
                      
                     
                         
                     
                      
                     
                       j 
                       ′ 
                     
                   
                 
               
               + 
               ⋯ 
               + 
               
                 
                   
                     n 
                     
                       mj 
                       ′ 
                     
                   
                    
                   
                     x 
                     
                       mj 
                       ′ 
                     
                   
                 
                 
                   T 
                   
                     mj 
                     ′ 
                   
                 
               
             
           
         
       
     
         [0000]    where j′ is the index of the other code (i.e.) if j=1, then j′=2 and vice versa. 
         [0053]    Under this system configuration, the analysis of delivery probability has to take into account
   1. Collisions between packets transmitted by nodes using the same code   2. Interference caused by the packets transmitted by nodes using a different code   
 
         [0056]    To calculate the delivery probability, P ij , of a node n ij  we proceed as follows. First, we calculate the probability of one transmission being successful. This is given by the product of the probability that no transmission which uses that same code occurs in the interval (t 0 −t f ; t 0 +t f ) and the probability that interference due to transmissions using the other code does not cause an error. Let the probability that interference does not cause an error be denoted by I j . Hence the probability that one transmission is successful is given by 
         [0000]      p s =p′ s I j   
         [0057]    Each node transmits x ij  times in the interval T i . Thus the probability that all the x ij  transmissions are in error is 
         [0000]        P   e =(1− p   s ) x     ij     
         [0058]    Thus the delivery probability, which is the probability that at least one of x ij  transmission is successful, is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     P 
                     ij 
                   
                   = 
                     
                    
                   
                     1 
                     - 
                     
                       P 
                       e 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     1 
                     - 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                               p 
                               s 
                               ′ 
                             
                              
                             
                               I 
                               j 
                             
                           
                         
                         ) 
                       
                       
                         x 
                         ij 
                       
                     
                   
                 
               
             
             
               
                 
                   
                     P 
                     ij 
                   
                   = 
                     
                    
                   
                     1 
                     - 
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             
                                
                               
                                 ( 
                                 
                                   
                                     - 
                                     2 
                                   
                                    
                                   
                                       
                                   
                                    
                                   
                                     λ 
                                     ij 
                                   
                                    
                                   
                                     t 
                                     f 
                                   
                                 
                                 ) 
                               
                             
                              
                             
                               I 
                               j 
                             
                           
                         
                         ) 
                       
                       
                         x 
                         ij