Method of Clustering Devices in Wireless Communication Network

Abstract

In a wireless communication network ( 200 ) comprising a base station ( 210 ) and a plurality of remote terminals ( 220 ), the plurality of remote terminals ( 220 ) are divided into a plurality of clusters ( 230 ) for communication with the base station ( 210 ), and each of the remote terminals ( 220 ) is assigned to a cluster ( 230 ) based on at least one characteristic, measured by one or more of the remote terminals ( 220 ), of one or more external signals transmitted by one or more external terrestrial transmitters ( 250 ) not associated with the communication network ( 200 ). Accordingly: a parameter of a communication between the base station ( 210 ) and each remote terminal ( 220 ) may be selected according to the cluster ( 230 ) to which each remote terminal ( 220 ) belongs; remote terminals ( 220 ) within a cluster ( 230 ) may be enabled to communicate directly with each other; and/or remote terminals ( 220 ) may be selected to perform frequency spectrum profile measurements of the frequency band used by the communication network ( 200 ) according to the clusters ( 230 ) to which they are assigned.

1 . In a wireless communication network ( 200 ) comprising a base station ( 210 ) and a plurality of remote terminals ( 220 ), a method of communication, comprising:
 dividing the plurality of remote terminals ( 220 ) into a plurality of clusters ( 230 ) for communication with the base station ( 210 );   assigning each of the remote terminals ( 220 ) to one of the clusters ( 230 ) based on at least one characteristic, measured by one or more of the remote terminals ( 220 ), of one or more external signals transmitted by one or more external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ); and   performing at least one of the following three operations:
 (1) selecting, according to a cluster ( 230 ) to which each remote terminal ( 220 ) belongs, at least one parameter of a communication between the base station ( 210 ) and each remote terminal ( 220 ); 
 (2) selecting, according to the clusters ( 230 ) to which they are assigned, which ones among the plurality of remote terminals ( 220 ) will perform frequency spectrum profile measurements of a frequency band used by the external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ); and 
 (3) selecting, according to the clusters ( 230 ) to which they are assigned, which ones among the plurality of remote terminals ( 220 ) will transmit to the base station ( 210 ) frequency spectrum profile measurements of a frequency band used by the external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ). 
   
   
   
       2 . The method of  claim 1 , wherein the at least one characteristic measured by the one or more remote terminals ( 220 ) comprises a frequency spectrum profile measured at each of the remote terminals ( 220 ) produced by the one or more external signals transmitted by the one or more external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ). 
   
   
       3 . The method of  claim 2 , wherein the frequency spectrum profile comprises a measurement vector,  x i   , of size 1*f where f is a number of channels assigned for defining the external signals transmitted by the one or more external terrestrial transmitters ( 250 ), where i is an index number of a corresponding remote terminal ( 220 ), and where j is an index number of a cluster ( 230 ). 
   
   
       4 . The method of  claim 3 , wherein the plurality of remote terminals ( 220 ) is n, and wherein dividing the n remote terminals ( 220 ) into a plurality of clusters ( 230 ) for communication with the base station ( 210 ) and assigning each of the n remote terminals ( 220 ) to one of the clusters ( 230 ) based on the measured characteristic of the one or more external signals comprises:
 ( 610 ) establishing a trial value of k=2 clusters ( 230 );   ( 630 ) assigning k of the n measurement vectors of the n remote terminals ( 220 ) as trial mean measurement vectors,  m j   , for each of the k clusters ( 230 );   ( 640 ) for each of the n remote terminals ( 220 ), determining which of the trial mean measurement vectors,  m j   , is closest to its measurement vector  x i    and tentatively assigning the remote terminal ( 220 ) to the corresponding cluster ( 230 ) j as a tentative assignment;   ( 650 ) for each cluster ( 230 ), j, calculating a new mean measurement vector  m j    using the measurement vectors for all of the remote terminals ( 220 ) tentatively assigned to the cluster ( 230 ) j in step ( 640 );   repeating steps ( 640 ) and ( 650 ) until there is no change in the values of the mean measurement vectors  m j   ;   ( 660 ) computing a total vector distance, J, between the measurement vectors  x i    for each of the n remote terminals ( 220 ) and the mean vector  m j    for the cluster ( 230 ) j to which the remote terminal ( 220 ) was last tentatively assigned in step ( 640 );   ( 670 ) comparing J to a maximum allowed value J*;   ( 680 ) when J is greater than the maximum allowed value J*; incrementing k by 1 and repeating steps ( 630 ) through ( 670 ) until J is less than or equal to the maximum allowed value J*; and   when J is less than or equal to the maximum allowed value J*; using the trial value of k as a number of clusters ( 230 ) into which the n remote terminals ( 220 ) are divided, and using the tentative assignments of step (c) to assign each of the n remote terminals ( 220 ) to one of the k clusters ( 230 ).   
   
   
       5 . The method of  claim 1 , wherein the at least one parameter of the communication between the base station ( 210 ) and the remote terminal ( 220 ) that is selected according to a cluster ( 230 ) to which the remote terminal ( 220 ) belongs comprises at least one selected from the group consisting of: an error correction code, a modulation format, a guard interval between adjacent transmitted symbols, and one or more frequency channels. 
   
   
       6 . The method of  claim 1 , wherein the at least one characteristic of the one or more external signals measured by the one or more remote terminals ( 220 ) comprises a time of arrival of a sync signal included in at least one of the one or more external signals transmitted by the one or more external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ). 
   
   
       7 . The method of  claim 6 , wherein the sync signal is a field sync sequence in a digital television (DTV) broadcast signal. 
   
   
       8 . The method of  claim 1 , wherein the one or more external signals transmitted by the one or more external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ) includes a television broadcast signal in a frequency channel in which the wireless communication network ( 200 ) operates. 
   
   
       9 . In a wireless communication network ( 200 ) comprising a base station ( 210 ) and a plurality of remote terminals ( 220 ), a method of communication, comprising:
 determining a location of each of the plurality of remote terminals ( 220 ) with respect to the base station ( 210 );   dividing the plurality of remote terminals ( 220 ) into a plurality of clusters ( 230 ) for communication with the base station ( 210 );   assigning each of the remote terminals ( 220 ) to one of the clusters ( 230 ) based on the determined location of each remote terminal ( 220 ) so as to group remote terminals ( 220 ) together in each cluster ( 230 ) according to their proximity to each other; and   selecting at least one parameter of a communication between the base station ( 210 ) and each remote terminal ( 220 ) according to a cluster ( 230 ) to which each remote terminal ( 220 ) belongs.   
   
   
       10 . The method of  claim 9 , wherein determining a location of each of the plurality of remote terminals ( 220 ) with respect to the base station ( 210 ), comprises, for each remote terminal ( 220 ):
 determining a distance, d 12 , between the base station ( 210 ) and the remote terminal ( 220 );   determining a distance, d 02 , between the remote terminal ( 220 ) and a known location of a television broadcast antenna; and   solving a pair of simultaneous equations using: (1) the distances d 12  and d 02 , (2) the known location of the television broadcast antenna, and (3) a known location of the base station ( 210 ), to determine the location of the remote terminal ( 220 ).   
   
   
       11 . The method of  claim 10 , wherein determining the distance, d 12 , between the base station ( 210 ) and the remote terminal ( 220 ) comprises:
 measuring a turnaround time interval, t 12 , for a token to be transmitted roundtrip between the base station ( 210 ) and the remote terminal ( 220 ); and   determining the distance, d 12 , from the turnaround time interval, t 12 .   
   
   
       12 . The method of  claim 10 , wherein determining the distance, d 02 , between the known location of the television broadcast antenna and the remote terminal ( 220 ), comprises:
 determining a time of arrival, t 1 , at the base station ( 210 ) of a sync signal included in a television signal transmitted by the television broadcast antenna;   determining a time of arrival, t 2 , at the remote terminal ( 220 ) of the sync signal included in the television signal transmitted by the television broadcast antenna;   determining a time interval, to 2, for the television signal to travel from the television broadcast antenna to the remote terminal ( 220 ) using the times of arrival t 1  and t 2  and a known distance d 01  between the base station ( 210 ) and the television broadcast antenna; and   determining d 02  according to the equation d 02 =t 02 *c, where c is the speed of light.   
   
   
       13 . The method of  claim 12 , wherein the television signal is in a frequency channel in which the wireless communication network ( 200 ) operates. 
   
   
       14 . The method of  claim 9 , wherein the at least one parameter of the communication between the base station ( 210 ) and the remote terminal ( 220 ) that is selected according to a cluster ( 230 ) to which the remote terminal ( 220 ) belongs comprises at least one selected from the group consisting of: an error correction code, a modulation format, a guard interval between adjacent transmitted symbols, and one or more frequency channels. 
   
   
       15 . In a wireless communication network ( 200 ) comprising a base station ( 210 ) and a plurality of remote terminals ( 220 ), a method of determining a location of each of the plurality of remote terminals ( 220 ) with respect to the base station ( 210 ), comprising:
 (a) determining a distance, d 12 , between the base station ( 210 ) and the remote terminal ( 220 ), based on a turnaround time interval, t 12 , for a token to be transmitted roundtrip between the base station ( 210 ) and the remote terminal ( 220 );   (b) determining a time of arrival, t 1 , at the base station ( 210 ) of a sync signal included in an external signal transmitted by an external terrestrial transmitter ( 250 ) located at a known location;   (c) determining a time interval, t 02 , for the external signal to travel from the external terrestrial transmitter ( 250 ) to the remote terminal ( 220 ) using: (1) a known distance d 01  between the base station ( 210 ) and the external terrestrial transmitter ( 250 ), (2) the time of arrival t 1 , and (3) a time of arrival, t 2 , at the remote terminal ( 220 ) of the sync signal included in the external signal transmitted by the external terrestrial transmitter ( 250 );   (d) determining a distance, d 02 , between the remote terminal ( 220 ) and the known location of the external terrestrial transmitter ( 250 ), based on the time interval to 2; and   (e) determining the location of the remote terminal ( 220 ) using: (1) the distances d 12  and d 02 , (2) the known location of the external terrestrial transmitter ( 250 ), and (3) a known location of the base station ( 210 ).   
   
   
       16 . The method of  claim 15 , wherein the external terrestrial transmitter ( 250 ) is a television broadcast transmitter ( 250 ) and the external signal is a television signal in a frequency channel in which the wireless communication network ( 200 ) operates. 
   
   
       17 . The method of  claim 15 , further comprising:
 (f) determining a time of arrival, t 3 , at the base station ( 210 ) of a sync signal included in a second external signal transmitted by a second external terrestrial transmitter ( 250 ) not associated with the wireless communication network ( 200 ) located at a known location;   (g) determining a time interval, t 23 , for the external signal to travel from the second external terrestrial transmitter ( 250 ) to the remote terminal ( 220 ) using: (1) the known distance d 13  between the base station ( 210 ) and the second external terrestrial transmitter ( 250 ), (2) the time of arrival t 3 , and (3) a time of arrival, t 4 , at the remote terminal ( 220 ) of the sync signal included in the second external signal transmitted by the second external terrestrial transmitter ( 250 ) not associated with the wireless communication network ( 200 );   (h) determining a distance, d 23 , between the remote terminal ( 220 ) and a known location of the second external terrestrial transmitter ( 250 ), based on the time interval t 23 ;   (i) determining the location of the remote terminal ( 220 ) using: (1) the distances d 12  and d 23 , (2) the known location of the second external terrestrial transmitter ( 250 ), and (3) the known location of the base station ( 210 ); and   (j) averaging the locations produced in steps (e) and (i) using the first and second external signals transmitted by the first and second external terrestrial transmitters ( 250 ) to more accurately determine the location of the remote terminal ( 220 ).   
   
   
       18 . The method of  claim 15 , further comprising:
 determining a time of arrival, t 3 , at the base station ( 210 ) of a sync signal included in a second external signal transmitted by a second external terrestrial transmitter ( 250 ) not associated with the wireless communication network ( 200 ), located at a second known location;   determining a time interval, t 23 , for the external signal to travel from the second external terrestrial transmitter ( 250 ) to the remote terminal ( 220 ) using: (1) the known distance d 13  between the base station ( 210 ) and the second external terrestrial transmitter ( 250 ), (2) the time of arrival t 3 , and (3) a time of arrival, t 4 , at the remote terminal ( 220 ) of the sync signal included in the second external signal transmitted by the second external terrestrial transmitter ( 250 ) not associated with the wireless communication network ( 200 ); and   determining a distance, d 23 , from the known location of second external terrestrial transmitter ( 250 ) to the remote terminal ( 220 ) based on the time interval t 13 ,   wherein determining the location of the remote terminal ( 220 ) using: (1) the distances d 12  and d 02 , (2) the known location of the external terrestrial transmitter ( 250 ); and (3) the known location of the base station ( 210 ), further comprises determining the location of the remote terminal ( 220 ) in three dimensions by further using (4) the known location of the second external terrestrial transmitter ( 250 ); and (5) the distance d 23 .   
   
   
       19 . In a wireless communication network ( 200 ) comprising a base station ( 210 ) and a plurality of remote terminals ( 220 ), a method of communication, comprising:
 dividing the plurality of remote terminals ( 220 ) into a plurality of clusters ( 230 ) for communication with the base station ( 210 );   assigning each of the remote terminals ( 220 ) to one of the clusters ( 230 ) based on at least one characteristic, measured by one or more of the remote terminals ( 220 ), of one or more external signals transmitted by one or more external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ); and   enabling each remote terminal ( 220 ) to communicate data directly with other remote terminals ( 220 ) in its assigned cluster ( 230 ) without passing the data through the base station ( 210 ).   
   
   
       20 . In a wireless communication network ( 200 ) comprising a base station ( 210 ) and a plurality of remote terminals ( 220 ), a method of communication, comprising:
 dividing the plurality of remote terminals ( 220 ) into a plurality of clusters ( 230 ) for communication with the base station ( 210 );   assigning each of the remote terminals ( 220 ) to one of the clusters ( 230 ) based on at least one characteristic, measured by one or more of the remote terminals ( 220 ), of one or more external signals transmitted by one or more external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ); and   selecting which ones among the plurality of remote terminals ( 220 ) will perform frequency spectrum profile measurements of a frequency band used by the external terrestrial transmitters ( 250 ) not associated with the wireless communication network ( 200 ), according to the clusters ( 230 ) to which they are assigned.