Monday, December 31, 2007

Mobile IP - Quick learn


A very short description of Mobile IP is given in this post:

Purpose of Mobile IP:
Keep the mobile node's IP address unchanged when mobile node moves

Main modules used in Mobile IP:
MN(Mobile Node) - has a permanent home address
CN(Correspondent Node) - a host in the traditional network
HA(Home Agent)
FA(Foreign Agent)
COA(Care-Of Address) - the 2nd IP address of the MN

How Mobile IP works:
1) MN first finds the FA's info (because FA broadcasts its information
periodically) - Agent Discovery
2) If MN is still in its HA's area, nothing to do with Mobile IP; else MN needs
to get a COA
3) MN registers the COA to its HA through FA (HA maintains a table,
including MN's COA) - Registration
4) HA sends data to FA through a tunnel - Tunneling
5) FA sends data to CN (MS's data is sent to CN through FA, not going back
to HA)

Further explanation:

Agent Discovery
Extend the ICMP (Internet Control Message Protocol) message
IRDP (ICMP Router Discovery Protocol) - automatically find the local router
1) HA/FA use ICMP/IRDP to broadcast their info - agent broadcast
2) MN sends the agent request (also in broadcasting)
How to determine the mobility? ("life time" in IRDP)
1) Agent sends IRDP including a "life time" field
2) MN compares the network prefix in the broadcast messages to check if it's
moved
3) if MN cannot receive any broadcast message
i) try to contact HA, as if it's back to HA
ii) try to use DHCP or manual configuration
Registration
MN -> FA -> HA (bind the 1st IP and the 2nd IP addresses together)
When MN returns HA, needs to cancel the registration

MN's Co-located COA: MN sends registration request to HA directly, tunneling is
from HA to MN, COA is MN's address
In this case, there's no FA and HA in the traditional network
(using DHCP/manual configuration to get 2nd IP)
PROS: no FA needed;
CONS: MN needs two IP addr, two overlapped IP protocol stacks

FA's COA: FA sends the registration request to HA for MN, tunneling is from HA
to FA, COA is the FA's address
PROS: multiple MN can share one COA, so IP address is saved;
CONS: need FA

Frequent registration: on the boundary of two networks
1) Data link layer solution:
Use layer-2 capability to manage the mobility, to reduce layer-3 mobility
2) Mobile IP multiple binding:
Similar as soft hand-over in CDMA
In HA, for one registered MN, binds multiple COAs for this MN (when MN is
on the boundary of multiple FAs)

Tunneling (data forwarding): assure transparent transmission
1) CN's information is still forwarded to HA (for CN, any MN is treated as if it
is fixed)
2) HA uses proxy ARP to capture this information
HA works as an agent of the MN to give the MAC back to the CN
3) Use tunnel to forward data to FA (FA records MN's MAC addr when MN is
registering)
4) Reverse data is delivered to CN directly

Functions of HA and FA:
HA:
1) Act as a router
2) Manage the MN's host routing (binding table, maintain different tunnel to
different COA)
3) Manage and operate tunnel's interface (encapsulate beared protocol and then
forward with bearing method)

FA:
1) Manage and operate tunnel's interface
2) Manage visited MN's list (in registration)
3) Use ARP to access MN (FA gets the original IP packet, but FA cannot access MN
directly since FA and MN are not in the same network, so FA needs to use ARP)

Encapsulation process in Mobile IP:
1) IP in IP encapsulation - an outer IP header is inserted to the front
2) Minimum encapsulation - reduce redundant information of the inner IP datagram
3) GRE (Generic Routing Encapsulation) - encapsulate a wide variety of network
layer packets inside IP tunneling packets

Monday, September 10, 2007

[Code] Non-recursive pre-order traversal of a tree

Traversal of a tree data structure often uses recursive algorithm. Without recursion, how to solve the problem? Here is the demo code I programmed in C.









001 #include <iostream>
002 using namespace std;
003 /** 
004   Definition of NODE of the TREE 
005 */
006 typedef struct NodeT
007 {
008   struct NodeT *left;
009   struct NodeT *right;
010   char data;
011 }NODE;
012 /**
013   Definition of Element of the STACK
014 */
015 typedef struct ElementS
016 {
017   struct ElementS *next;
018   NODE *data;
019 }ELEMENT;
020 /** 
021   recursive version of Pre-order traversal
022   void PreOrder(NODE * root)
023   Algorithm:
024     Print out the ROOT's value
025   Do a pre-order traversal on the LEFT sub-tree of the ROOT node
026   Do a pre-order traversal on the RIGHT sub-tree of the ROOT node
027 */
028 void PreOrder(NODE * root)
029 {
030   if (root)
031   {
032     cout << root->data << "->" ;
033     PreOrder(root->left);
034     PreOrder(root->right);
035   }
036   else
037     return;
038 }
039 /** 
040    non-recursive version of Pre-order traversal
041    void PreOrderNonRecur(NODE *root)
042    Algorithm:   
043    create a stack
044      PUSH the root node of the tree into the stack
045      While the stack is not empty
046      POP a node
047      If the node is not NULL
048        Print the value of the node
049      PUSH the node's right child into the stack
050      PUSH the node's left child into the stack
051 */
052 bool CreateStack(ELEMENT **stack)
053 {
054   *stack=NULL;
055   return true;
056 }
057 bool DeleteStack(ELEMENT **stack)
058 {
059   ELEMENT *next;
060   while(*stack)
061   {
062     next=(*stack)->next;
063     delete *stack;
064     *stack=next;
065   }
066   return true;
067 }
068 bool Push(ELEMENT **stack, NODE *data)
069 {
070   ELEMENT *p = new ELEMENT;
071   if(!preturn false;
072   p->data = data;
073   p->next = *stack;
074   *stack=p;
075   return true;
076 }
077 bool Pop(ELEMENT **stack, NODE **data)
078 {
079   ELEMENT *p;
080   p=*stack;
081   if(!preturn false;
082   *data = p->data;
083   *stack= p->next;
084   delete p;
085   return true;
086 }
087 void PreOrderNonRecur(NODE *root)
088 {
089   ELEMENT *theStack;
090   NODE *data;
091   NODE *curNode;
092 
093   CreateStack(&theStack);
094   Push(&theStack, root);
095 
096   while(Pop(&theStack, &data))
097   {
098     curNode = data;
099     if(curNode)
100     {
101       cout<<curNode->data<<"->";
102       Push(&theStack, curNode->right);
103       Push(&theStack, curNode->left);
104     }
105   }
106   DeleteStack(&theStack);
107 }
108 void main()
109 {
110   NODE a,b,c,d,e,f,g;
111   /** 
112     manually construct the tree
113   */
114   a.left=&b;
115   a.right=&c;  
116   b.left=NULL;
117   b.right=&d;
118   c.left=&e;
119   c.right=&f;
120   d.left=&g;
121   d.right=NULL;
122   e.left=NULL;
123   e.right=NULL;
124   f.left=NULL;
125   f.right=NULL;
126   g.left=NULL;
127   g.right=NULL;
128   a.data='a';
129   b.data='b';
130   c.data='c';
131   d.data='d';
132   e.data='e';
133   f.data='f';
134   g.data='g';
135 
136   cout<<"Recursive pre-order traversal of the tree: "<<endl;
137   PreOrder(&a);
138   cout<<"End of traversal";
139   cout<<endl;
140 
141   cout<<"Non-recursive pre-order traversal of the tree: "<<endl;
142   PreOrderNonRecur(&a);
143   cout<<"End of traversal";
144   cout << endl;
145 }
146 /**
147   the output should be
148   a->b->d->g->c->e->f->END
149 */

Saturday, September 1, 2007

[WiMAX] Fundamentals of WiMAX - (6)

We have introduced the basic idea of OFDM before. In this post, we will discuss OFDMA (Orthogonal Frequency Division Multiple Access) in Q&A style.

Q: What's the relationship between OFDM and OFDMA?
A: OFDMA can be considered as a version of OFDM optimized for multiple users. The basic idea behind OFDMA is Sub-Channelization, i.e. assigning subsets of subcarriers to different users.

Q: What's the advantage of OFDMA over OFDM?
A: We know OFDM has immuity to frequency-selective fading channel because it breaks a single high data rate stream into multiple low data rate streams, thereby the subcarrier's bandwidth is smaller than the coherence bandwidth of the channel. For a wireless system with multi users, the total system resources are shared by all users. However, in one time slot, OFDM only assigns the whole resource to only one user, i.e. one user occupies all subcarriers in one time. This makes OFDM not efficient in resource allocation. A new multiple-access technique becomes necessary. This is the purpose of OFDMA. By allowing users share subcarriers and time slots, additional flexibility can be provided by OFDMA: multi-user diversity. In addition, adpative modulation can be used in OFDMA for different users according to channel condition.

Q: How is the 'Sub-Channelization' realized?
A: In OFDMA, the sub-carriers are divided into groups of sub-carriers. Each group is called a sub-channel. The sub-carriers that form a sub-channel need not be continuous. Based on their channel conditions and QoS requirements, different sub-channels can be assigned (scheduled) to different users. This multiple access is performed before the IFFT operation, thereby the scheduling algorithm used for OFDMA is realized in both frequency and time domain.

(to be continued)

Thursday, August 2, 2007

Redirect homepage too fast makes cookie setting failed in IE7

Yesterday I got a problem of setting cookies with Javascript in IE7. The cookie string was always generated successfully, but the cookie could not be stored by IE7. I set the privacy level of IE7 to "Accept all cookies", but it doesn't work yet. A simplified demo of the Javasript code is listed below:







<script language="JavaScript">
    var name="visitor";
    var value=Math.random();
    var today = new Date();
    var expires=new Date(today.getTime()+(86400*1000));
    var path="";
    var domain="";
    var secure="";
    var cookieString = name + "=" +escape(value
       ( (expires";expires=" + expires.toGMTString() ""
       ( (path";path=" + path : ""
       ( (domain";domain=" + domain : ""
       ( (secure";secure" "");  
    document.cookie = cookieString;
</script>
<html><head><META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://www.google.com"></head></html>




Finally I found the reason. In order to store the cookies in IE7, you must manually "allow the active contents" to run.

However, the code <META HTTP-EQUIV="Refresh" CONTENT="0; URL=http://www.google.com"> refreshes the webpage too fast and thus you cannot unblock the active contents in time.

For <META HTTP-EQUIV="Refresh" CONTENT="n;url" > , n means the number of seconds to wait before loading the specified URL. If we increase this n (e.g., let n=10 ), then we will have enough time to unblock the active contents, and then the cookie can be stored successfully.

Tuesday, July 24, 2007

[Wireless] Avis Connect - Auto Wi-Fi

Last Saturday in San Jose's International airport, I found Avis (a rental car company) is providing a service called auto Wi-Fi. The device looks like a cable modem with two antennas. It says then you can connect to the Internet everywhere you go. The price is $10.95 per day, which is really cheap compared with other paid Wi-Fi services. I'm a little surprised how it works to provide Wi-Fi service when driving, because Wi-Fi is just a short range system and needs to connect itself to a 'real' Internet access network. Mobile WiMAX can connect to Internet direclty but as I know currently the WiMAX network is still under construction.

When I came back home, I checked the Internet and found the answer: it is a combination of a Wi-Fi router and a high-speed cellular modem. The access to the Interent uses a patent-pending, enhanced-reception technology from Autonet Mobile, which roams among existing 3G cellular networks and can switch seamlessly between neighboring networks and high/low-speed connections as needed without interrupting the session. This idea is pretty smart.

Autonet promises the service will work on 95 percent of U.S. roads in the future. It sounds pretty good. Next time for traveling by car, I will have a shot and check how the service is going.

Thursday, July 12, 2007

[WiMAX] Fundamentals of WiMAX - (5)

In this post, let's take a quick look of the standardizations of WiMAX.

IEEE 802.16 Group was formed in 1998, its inital focus is to develop an air-interface standard for a LOS-based point to mulitpoint wireless broadband system working in 10G-66GHz band. In 2001, the original 802.16 standard was completed. After that, the task group produced 802.16a, which is an amendment to 802.16. This 802.16a is for NLOS applications in the 2G-11GHz band. Further revision is IEEE 802.16-2004 (fixed WiMAX), which replaced all previous specifications and formed the first version of WiMAX standard. It targeted fixed applications. In order to support mobile services, in 2005 a new amendament to IEEE 802.16-2004 called IEEE 802.16e-2005 (Mobile WiMAX) was approved by IEEE.

In short, WiMAX uses OFDM in the physical layer. The difference of the two specifications is: IEEE 802.16-2004 uses fixed-FFT-size OFDM, but IEEE 802.16e-2005 uses scalable OFDMA. Therefore, for fixed WiMAX, because FFT size is fixed, the subcarrier spacing will increase with larger bandwidth, and then the symbol time will decrease. It implies that a larger portion of OFDM subcarriers is needed as guard time to overcome delay spread of the channel, which means spectral efficiency is lowered. In the contrast, for mobile WiMAX, the subcarrier spacing is fixed but the FFT size is adjustable. This scheme can be used to balance to requirements of delay spread and Doppler spread of the channel for different operating environments.

In addition to OFDM, in physical layer WiMAX also supports some optional advanced techniques for increasing the link performance and reliability. These techniques include powerful FEC - Forward Error Correction coding (such as Turbo coding and LDPC - Low Density Parity Check code, which is very close to the Shannon channel capacity), channel interleaving, multiple antenna techniques - MIMO (please refer to Fundamentals of WiMAX - (3) ) and adaptive modulation. From here you can see that WiMAX almost integreted the most popular and advanced techniques of digital communications together. This is an advantage of creating a new system, because you do not have too much back-compatibility issues to take into account.

Another big portion of WiMAX's standard is specifying the MAC layer functions between the lower physical layer and the upper network and transport layers. The MAC layer should be able to accommodate different traffic types, support QoS (Quality of Service), provide security and mobility and so on. Those are just common functions and are considered in almost every wireless system. The distinct part of WiMAX's MAC layer from other similar systems is on the scheduling and channel-access schemes. In downlink, the Base Station allocates dedicated or shared resources periodically to each subscriber station. Then each MS will use this allocated rresource to request bandwidth. This procedure is called Polling. Polling can be done with unicast or multicast. In uplink, WiMAX specifies a contention access and resolution scheme for multiple MSs accessing the shared resource. If one MS already has an allocation for traffic sending, it will not be polled. But it can be allowed to request more bandwidth.

Thursday, July 5, 2007

Is iPhone a phone?

The long rumored iPhone has finally arrived. Someone tore down the iPhone and found the processor is using ARM chips, the ROM and RAM are from Samsung, and the touch screen is made by Epson Imaging Device Corp. They estimated the hardware cost of 8GB iPhone will be about $270, which means the margin is about $330. Of course the margin cannot be that high, because the development cost is not taken into account. But it can be anticipated that the profit will be considerable.

So many reviews have been posted on the Internet officially by some evaluation groups or personally by Apple fans after June 29. No doubt some Apple fans shouted acclaims and some others attacked its shortcomings severely. I cannot afford buying an iPhone, but I'll try to give my two cents here based on the reviews I have read recently.

Basically, iPhone is not just a cell phone, it is even not just a smart phone. It innovates the UI (user interface) in a revolutionary way, which makes it so distinct. Although it lacks some functions that some ordinary handsets or smart phones are supporting, such as no voice dialing, no speed dialing, no games, only supports GSM and EDGE etc, its defects cannot obscure the virtues. The reason is that Apple does not have too much experience and technique accumulations on cell phone design, but it grows fast.

Shortly put, the applications of iPhone can be enhanced, the bugs can be fixed, and the services can be enriched gradually. They will not be problems as long as people have belief on it. Especially from the view of the psychology, Americans love to see a burgeoning force challenges the conventional world and finally gets the success (Google is a lively example). Of course, those big guys in handset industry will not await their dooms. They will fight back definitely. For customers, this will always be a good news. For Apple, the next generation iPhone will be critical and crucial. People can forbear the weakness even flaw of the new product, but cannot tolerate them again. I guess Apple alreay noticed this kind of issue. So, we'll see.

Tuesday, June 19, 2007

[WiMAX] Fundamentals of WiMAX - (4)

Today we are talking about another important technique used in WiMAX - OFDM.

From the characteristic of the channel propagation in wireless environment, we know that delay spread caused by multipath fading will generate severe Inter Symbol Interference (ISI) for high data rate transmission, because the symbol time is inversely proportional to the data rate. As we mentioned before (Why OFDM for WiMAX and B3G?), you can use CDMA technology with Rake receiver to solve this problem, but it elicits two new problems: one is that the complexity is high, another is that you may need a huge bandwidth to get the essential spreading gain. For WiMAX system, the second problem is more difficult to handle with. But for UWB (Ultra Wide Band) system, it is achievable. So that's why one of the UWB's candidate PHY proposal is using spreading spectrum technique (DS-UWB).

Fortunately, a smart multi carrier modulation scheme called OFDM can support high data rate effectively. The basic idea of OFDM is simple: if you can not change the channel, you can change the signal to adapt to it.

We know in order to have a channel that does not have ISI, the symbol duration should be larger than the delay spread (or equivalently, the signal bandwidth should not exceed the coherence bandwidth). If we can divide the high rate date stream into M lower-rate substreams, then each substream will have larger subsymbol duration. If the subsymbol duration exceeds the delay spread, it hence is ISI free. Euqivalently, in this scenario, each substream's bandwidth is lower than the coherence bandwidth of the channel. However, simply dividing the high rate stream to lower-rate streams is just like the conventional mulit carrier technique, you have to insert guard band between subcarriers, which leads to very inefficient use of the available spectrum. OFDM solves this problem by overlapping subcarriers. Of course, you can not overlap subcarriers arbitrarily, because overlapping introduces crosstalk between subcarriers. But, if those subcarriers can overlap in orthogonality, great, the crosstalk vanishes!

A block diagram of OFDM system is shown in the following figure:



The modulator part is illustrated as follows:



And a simplified baseband model of passing an OFDM signal through the channel is demonstrated in the next figure:



Finally, the time-frequency block structure of the OFDM signal is shown in the figure below (where CP means cyclic prefix, whose length should be larger than the maximum delay spread of the channel):

Thursday, June 7, 2007

War without smoke - LTE, UMB, WiMAX...

"OFDMA TDD WMAN", the new name of a subset of WiMAX, was recommended by ITU-R as an IMT-2000 radio technology last week. It's a good news for WiMAX. Someone said: WiMax Gets ITU Standards Boost. Yes, it is. But, still a long way to go.

Let's take a look at how many candidate technologies we may have for the future:
LTE of 3GPP, UMB of 3GPP2, WiMAX, Mobile WiMAX/WiBro, IEEE802.20...

Ericsson said they abandoned WiMAX and would focus on LTE only, Qualcomm must be supporting UMB and they claimed they have many patents on OFDM/WiMAX, they also proposed IEEE802.20, Korea will continue working on the WiBro, even in the wired acccess area, there will be some Passive Optical Networks (PON) emerging in the future...

So who will win this war? Nobody knows, and it is impossible that one of them beats all others. I think some of them must be co-existing. But, the following answer should always be true: " It's something unpredictable but in the end USER's right. " (Lyrics of the Time of your life by Green Day) :-)

Monday, June 4, 2007

Capacity of ad hoc networks

Unlike the conventional cellular networks with single hopping from every terminal to
the base station, traffic in ad hoc networks may be relayed via intermediate nodes to the distant destination. The advantage of this multi-hop communication scheme is: the required transmission power can be reduced exponentially with shortened transmission distance, and more concurrent transmissions may be available in the whole network because of spatial reuse of the resource, such as frequency or channelizing codes. However, it is very difficult to achieve the best of both worlds. With shortened transmission link, the number of hops from the source to the destination increases too. Partial system bandwidth must be used to deliver those relayed traffic. On the other hand, more concurrent transmissions result in increased number of interferers. Therefore, one of the fundamental challenges in ad hoc network research is what capacity can be achieved and how to achieve it.

Capacity of a network means the theoretical bounds on the performance under perfect network operation. Generally speaking, capacity or throughput analysis of wireless ad hoc networks may be explored in the following three ways:

1) The first solution is to find the exact capacity region (defined as closure set of feasible rates) in the perspective of information theory as in the conventional cellular network.

However, it is very difficult to obtain the exact capacity region because multiple nodes in the network can cooperate in very complicated and sophisticated ways. As an example, even the capacity of the simplest relay channel, which consists of just three nodes, a source, a relay and a destination, is not fully solved yet.

Recently, a breakthrough on the network information theory was obtained in [Xie 04]. With the assistance of the Max-Flow Min-Cut lemma, the authors indicate that the network capacity is always upper bounded by sum of total power used by the transmissions of all the nodes in the network.

2) The second method is to study the long term available throughput coarsely, e.g. analyzing the asymptotic capacity and scaling law with respect to the network size.

This method recently gained much attention, although it is coarser than the first one. The well-known result is given by [Gupta 00], who demonstrates that capacity per user goes to zero as the number of the nodes per unit area goes to infinity. This is a pessimistic result, because it means large ad hoc network’s capacity is poor.

After Gupta’s work, many people engaged in the ad hoc network capacity and tried to find a better solution. One important paper is the one written by Grossglauser and David Tse in 2002. The policy is, introduce the mobility of nodes into traffic transmission. Source node will first transfer to near relays, and those relays will not transmit to desired destinations until they move close. The throughput can be increased to the order of N, but the delay is too high.

Recently an interesting paper [Jafar-tit05] shows that too much mobility may limit the capacity of ad hoc networks. His argument is when mobility is too high, the node cannot track the channel in time to get the instantaneous CSI, then makes it difficult to distinguish between nearest neighbors and distant nodes at each moment.

3) The third one is measuring the practical throughput under some specific configurations by numerical simulation.

Many great simulation platforms have been developed for this purpose and a lot of research work can be found in this area. Some well-known examples are Network Simulator 2 (NS2), OPNet, QualNet (commercial version of Glomosim) etc.

NS2 is free to use, but OPNet and QualNet require licenses. I used NS2 for about more than one year. The learning curve is a little bit long. If you just want to use existing funcational modules to run simulation, it's not too hard. You can use TCL/OTCL to set up environment and parameters. If you want to modify the existing modules or add something new, you have to know how to interface TCL/OTCL with C++, because the kernel of NS2 is programed in C++.

However, when I used it, the version 2.28 has a problem in the interference and noise calculation in the physical layer: the SNIR (Signal to Noise and Interference ratio) is not recalculated every time the interference changes. A paper given by Mineo Takai addressed this problem in depth. Fading channel was not supported either. Someone made an extension with Rayleigh and Ricean fading but it only worked with old version. Fortunately, I found a solution by modifying some lines of the source code. Moreover, a difficult thing is how to compare your results with other guys'. Especially when you modified the program, no one knows if your modification can be justified (I think most of the simulators have the similar problem, but commercial platforms may be better because they keep the consistency well). So finally I abandoned it.

Sunday, May 27, 2007

[WiMAX] Fundamentals of WiMAX - (3)

Today we are talking about one of the two core technologies of WiMAX: Multiple Antenna Techniques (let's abbreviate in MAT). Another important one is OFDM, which will be deferred to next topic. Like all 3G systems picked CDMA, we can anticipate that perhaps almost all upcoming 4G systems will employ OFDM and MIMO (Multiple Input Multiple Output) techniques. (Recent an interesting news is that Qualcomm just gave a tough talk on the patents of 4G. )

What can MAT provide? Generally speaking, MAT supports
1) spatial diversity,
2) beamforming,
3) and spatial multiplexing.

In old times (1970s), people only use multiple antenna in receiver owing to the cost and size consideration. In this case, with selection combining or maximal ratio combining (MRC), the performance under fading environment can be improved significantly due to receive diversity.

Later, people noticed that using MAT with beamforming can concentrate the power of the desired signal in a specific direction and lower down the interference to other links away from this direction. This is especially useful for multi user network. They call it smart antenna technique. One example is the TD-SCDMA system in 3G area.

In the late of 1990s, a key breakthrough was made for MAT. Transmit diversity schemes were invented, such as the space-time block code (STBC). Now the promising area of MAT is the spatial multiplexing.

For the receive diversity, you can find it from most of the wireless communication books. So we will focus our concentration on the transmit diversity and beamforming.

1) Transmit diversity
There are two types of transmit diversity, one is open-loop, another one is closed-loop. Open-loop means at the transmitter you don't need a feedback for the channel state from the receiver. On the contrary, closed-loop requires it. Thus you should guarantee the channel is with reciprocity. In some cases, you can assume the channel to be reciprocal, although it isn't.

Open-loop transmit diversity
The most popular open-loop transmit diversity scheme is STBC, where a special coding scheme (called Alamouti code, name of the inventor, who is currently the CTO of Intel's Mobility Wireless Group) is used in the transmitter. In short, a Nt*Nr STBC achieves the same diversity order and data rate as a Nr*Nt receive diversity system with MRC, but with a 10*log_10(Nt) transmit power penalty because of Nt transmit antennas.

For WiMAX or other OFDM-based system, the space/time coding can be coded over adjacent subcarriers rather than time slots.

Closed-loop transmit diversity
In this case, channel state information(CSI) is required at the transmitter. Because channel changes quickly in a highly mobile scenario, it is difficult to track the channel state in time and feedback it to the transmitter. Therefore, closed-loop transmit diversity tends to be suitable for fixed or low-mobility scenarios. Two important closed-loop schemes are: transmit selection diversity (TSD) and linear diversity precoding (LDP).

In TSD, only a subset of Nt transmit antennas are selected with good CSI, thereby comparing with STBC, TSD has less transmit power penalty because fewer transmit signals are sent.

In LDP, a linear precoder is used at the transmitter and a linear postcoder is applied at the receiver. They are used to improve the link reliability and can achieve higher SNR than the open-loop schemes.

Friday, May 25, 2007

Free talk - Analogy between wireless network and society

Today when I was on the metro bus, an idea jumped into my mind: there is some similarity between the wireless network and the human society.

For example, a sensor network with data aggregation is as a community, a cellular network is like a country ruled by a dictatorial government, a pure ad hoc network can be considered with Anarchism (means abolition of governments), and a network with multiple access points is like a society with democracy (some nodes are 'elected' as access points).

The interesting thing is, what is good for the administration of the society, republic, federal , democracy or autocracy? Similarly, which network topology is effective for a wireless network? Why the existing mobile networks use the cellular architecture? Why most 802.11 networks are configured in IBSS (Infrastructure Basic Service Set)? Think about it...

Saturday, May 12, 2007

[Wireless] Why OFDM for WiMAX and B3G?

In the beginning of 3G (Third Generation) era, CDMA technique was widely employed for most systems. For instance, 3GPP selected WCDMA (Wideband CDMA) for FDD mode, TD-SCDMA for TDD mode; 3GPP2 extended cdmaone to CDMA2000. The main reason is to support higher data rate wireless service in 3G systems than that in 2G systems.

Wideband CDMA system has a large bandwidth, which can be used to achieve frequency diversity. However, there exists a contradiction between the large bandwidth and high data rate which can be shown in the following simple diagram:

Wide bandwidth -> frequency selective channel -> causes large delay spread in time domain
High data rate -> small symbol interval -> experiences serious Inter Symbol Interference

For CDMA system, in order to combat this multipath delay spread, usually it has to resort to the sophisticated RAKE receivers, which resolves multipath using muliple fingers.

However, when wireless system goes to the broadband era, wideband CDMA may not be adequate. Even 3GPP proposed HSPDA/HSUPA to support data rate up to 14.4M/5.8Mbps in 5MHz channel , 3GPP2 proposed 1xEV-DO for data rate 3.1M/1.8Mbps (revision A), 4.9M/1.8Mbps (revision B) in 1.25MHz channel, their capability of supporting much higher data rate is limited. One reason is that they have to use multiple codes simultaneously, which may result in self-interference.

That's why in B3G (Beyond 3G), LTE (Long-term evolution) of 3GPP and AIE (Air Interface Evolution) of 3GPP2 both pick OFDM combining MIMO instead of CDMA. Similarly, in IEEE802.11 series, the low date rate is working on CDMA (802.11b) but high date rate uses OFDM (802.11g and 802.11a). WiMAX is also using OFDM.

Tuesday, May 8, 2007

[WiMAX] Fundamentals of WiMAX - (2)

In this part, we are going to give an overview of the wireless channel that may be experienced by WiMAX.

Generally speaking, the basic and important issues of wireless channel contain three aspects: pathloss, large-scale Shadowing and small-scale fading. You can find detailed descriptions of them in most of the books regarding wireless communications (chapter 4 and 5 of [1]). In summary, pathloss is inversely propotional to the distance between the transmitter and the receiver, Shadowing is mainly caused by obstructions within the propagation environment and is often log-normal distributed, small-scale fading is caused by multipath reflections (modeled by delay spread or coherence bandwidth) or motion between the transmitter and the receiver (modeled by Doppler frequency shift or coherence time).

So we will skip those fundamentals issues and assume that you have already known them very well. However, channel also varies over space if multiple antennae are used. Multiple antenna techniques emerged as a breakthrough in the last several years and some traditional books may lack of description on this part, thereby next we will give an outline of the spatial aspect of wireless channels.



Angular Spread

Like delay spread or Doppler spread, a parameter used to model the channel in space is the angular spread. It refers to the statistical distribution of the arriving signal's angle. A small angular spread means the received signal's energy is more focused, which implies less statistical diversity; contrarily, large angular spread means more statistical diversity available.

Coherence Distance

The dual of angular spread is coherence distance. A coherence distance Dc means that any physical positions separated by Dc have an uncorrelated received signal amplitude and phase. Coherence distance is often related to the wave length. Thus, higher frequency system has shorter coherence distance.

Coherence distance is often used to specify how far apart antennae should be separated to make received signals statistically independent. Small coherence distance means antenna array can be easily applied to provide rich diversity. This is particularly useful for mobile terminals which has the size constraint. Large coherence distance implies that large separation between two antennas is needed. In this case, it would be preferable to use beamforming with antenna array.

Channel model for OFDM

Since WiMAX is using OFDM, the channel model with multidimension correlation should be considered. When channel is highly frequency selective, it requires a large number of closely spaced subcarriers to combat the ISI (Inter Symbol Interference). On the other hand, when the channel is with large Doppler frequency shift (high mobility), it will degrade the subcarrier orthogonality. In the frequency domain, it will cause significant ICI (Inter Carrier Interference) as subcarriers become more closely spaced.

Emperical model

An emperical channel model for MIMO was proposed and developed by 3GPP (Third Generation Partnership Project). It is described in the technical report TR 25.996 [2]. This model can be used for systems such as WiMAX, 802.11n and 802.20 which use MIMO techniques.

Reference:
[1] Theodore S. Rappaport, "Wireless Communications: Principles and Practice (2nd Edition)," Prentice Hall PTR, December, 2001
[2] Spatial channel model for Multiple Input Multiple Output (MIMO) simulations http://www.3gpp.org/ftp/Specs/archive/25_series/25.996/

Sunday, May 6, 2007

[WiMAX] Fundamentals of WiMAX - (1)

WiMAX (Worldwide Interoperability for Microwave Access) is one kind of wirless broadband access technology. In my country, China, WiMAX is going to be deployed for the 2008 Olypmic games. Actually, in China there is another technology called McWill (Multicarrier Wireless internet Local Loop), which is a synchronous CDMA system using Smart Antenna , SWAP signaling , synchronous CDMA and Software Radio. This McWill is developed by a Chinese company. I remembered in the end of 2006, the news said McWill would be used for 2008 Olympic games. However, just after several months, the latest news says that WiMAX is authorized by the committe of the Olympic games and China Mobile is goint to deploy it in 2008. It looks like McWill lost the game. It is really a pity.

Ok, let us go back to our topic and concentrate on techniques. From today, I'm going to give a series of introduction of WiMAX, mainly focuses on its fundamental issues, such as overview, history, technicall challeges, physical layer, MAC layer etc. I think it also helps me consolidate my knowledge on WiMAX.

History of WiMAX

Before WiMAX, there already exist many wireline broadband access techniques, such as DSL(Digital Subscriber Line), cable modem, FTTP(Fiber to the premises ) and VDSL. This market grows quickly. When I came to the US in 2001, the rate of Verizon's is about 768Kbps. Now I'm using Comcast's cable modem with rate 5Mbps. Recently, Verizon is promoting its FIOS system which is said to support rate at 15-40Mbps.

Later, people found it is necessary to provide broadband access service in wireless, because it offers additional benifits and convenience. For example, it may be easier to install than wire-line access, the cost may be lower, it can be portable and mobile.

Generally speaking, wireless broadband access can be categorized into two types:
1) Fixed wireless broadband,
2) Mobile broadband.

As for WiMAX, it has evolved through four stages. [1]
1) Narrowband WLL (Wireless Local Loop) system
2) First generation LOS (Line of Sight) broadband system
3) Second generation NLOS (Non Line of Sight) broadband system
4) Standard-based broadbank system.

Next, let us take a quick look of those four stages.

1) Narrowband WLL

It is mainly based on DECT or CDMA. As I know, WLL on CDMA at 450MHz has been using in China for a long while.

2) LOS

In 1990s, LMDS(Local Multipoint Distribution System), works on 2.5 or 3.5GHz. Operator: Nextlink. Now it is almost dead. [2]

In late 1990s, MMDS(Multichannel Multipoint Distribution System), works on 2.5GHz. Operators: MCI, Sprint.

Starting in 2006, MMDS frequencies in the 2110-2155 MHz range are being re-allocated for the Advanced Wireless Services (AWS-1). [3]

3) NLOS

It is proposed to overcome the LOS issue, and improve link performance under multipath conditions. It may use OFDM, CDMA or multiantenna techniques.

4) Standard-based

It is the well-known IEEE 802.16x [4], a seriers of standards for Wireless Metropolitan Area Network (WMAN).

  • December 2001, IEEE 802.16 standards completed for > 11GHz.
    Wireless WAN-SC, uses single carrier modulation techniques. MAC layer is with TDM.
  • January 2003, IEEE 802.16a standard completed.
    Works in the 2GHz to 11GHz range, enables NLOS deployments by using OFDM. MAC is using OFDMA.
  • June 2004, IEEE 802.16-2004 standard completed and approved.
    It replaces 802.16, 802.16a, 802.16c with a single standard. It is also called Fixed WiMAX.
  • December 2005, IEEE802.16e-2005 approved.
    Supports vehicular mobility applications. It is also referred to as Mobile WiMAX.

Similar to 802.11x, IEEE established the specifications for WiMAX but left to the industry the task of converting them into an interoperable standard and the task of certification. WiMAX Forum (analogous as Wi-Fi Alliance) was formed to do those tasks.



References:
[1] J.G.Andrews, Arunabha Ghosh and Rias Muhamed, "Fundamentals of WiMAX-understanding Broadband Wireless Networking", Prentice Hall, Feb, 2007

[2] http://en.wikipedia.org/wiki/MMDS

[3] http://en.wikipedia.org/wiki/LMDS

[4] http://en.wikipedia.org/wiki/Wimax

Saturday, April 28, 2007

Export figure to pdf in Matlab

In LaTex, if the figure is in pdf format, you can click pdfLaTex just once to generate the output. Otherwise, if the figure is in eps format, you have to click button three times to do the same thing by using the LaTex -> dvi2ps -> ps2pdf workflow.

The good thing is, Matlab can export figure to pdf format. Unfortunately, when saving a figure to a pdf file in Matlab, you'll find the figure doesn't fit the layout very well, i.e. there is a large margin from the figure to the page boundary. Those margins will be inserted into the LaTex output when you include these pdf figures.

A solution is:
1) After you plot the figure in Matlab, go to 'File->Export Setup', input the size of the output you want, e.g. Width: 6 inches, Height: 5 inches. Then click 'Apply to Figure' button.
2) Don't close the 'Export Setup' window. Go to 'File->Print Preview->Paper', input the same size in the Width and Height options.
3) Don't close the 'Print Preview' window. Go back to the 'Export Setup' window, and click 'Export', then select pdf format and save it.
4) Check the output pdf file, you'll see it is perfect.

Friday, April 27, 2007

Making Slides Using LaTex

Recently I'm preparing for my dissertation slides. I used to create transparencies with PowerPoint because of its simplicity, but it is really difficult to cope with mathmatical equations. You have to reserve space for equations in the text, and if you modify some equations later, you may have to readjust their reserved space one by one.

So I transfer to LaTex, although I need some time to learn it, it is powerful. It has rich overlay and dynamic effects. The layout, the colors and the fonts can easily be changed. The most important thing for me is that it can merge text and mathematical formulae smoothly and can reuse LaTex codes of my previous papers.

There are some well-known existing packages for slides making in LaTex, such as Beamer, Proper, Foiltex etc. I didn't spend too much time on investigating and comparing those packages pros and cons. I just select the Beamer.

After half day's learning, I can create slides with Beamer quickly. Beamer can handle graphics but with less flexibility, e.g. locating the position of figures freely is not that easy. Fortunately, I found another package called 'pstricks' which can do this kind of work easily. However, pstricks does not support PdfLaTex. The workflow of pstricks is LaTex->dvips->pspdf.

The following figure is a demo of the slides created by Beamer.

Wednesday, April 25, 2007

Error LNK2001: unresolved external symbol...

Recently, when I used the templates in C++, I got a link error: unresolved external symbol "public: __thiscall ...". My work has three files: fc.h, fc.cpp and main.cpp.







------------------------------------------------

// fc.h

template <class T>

class fc

{

    public:

       func();

};

// end of fc.h//

------------------------------------------------

// fc.cpp

template <class T>fc <class T>::func() { }

// end of fc.cpp//

------------------------------------------------

// main.cpp

#include "fc.h"

int main()

{

    fc A;

    A.func();

}

------------------------------------------------







However, when I removed the template declaration from the header file, or put all three files just in one body, the link runs smoothly. Finally, I found the reason and the solution of this kind of problem from the Internet [1].

At least three cases are related to this link error:
1. Forget to define a declared member function, especially the constructor.
2. Static member or class.
3. Using template with splitted declaration and definition.

For the first scenario, in general, people will not forget to define a member function after the declaration. So this kind of link erro seldom appears. But sometimes people may have declared the constructor but forget the definition and think the system will do it automatically. It is right that system may creat the default constructor if you don't declare it. But this doesn't work when the declaration has been made.

For the second case, if a class has a declared static member, because you cannot initialize it inside the class body (it belongs to the class, not the object), so if you forget defining this static member outside the body, the link error will also occur.

The thrid one is the well-known fallacy: templates behave similarly as ordinary classes and functions with respect to the separation between their declarations and definitions. This is not true. The reason is that a template actually is NOT real code. A good anologic example is: the MS-Word has some letter templates, but they are not real letters until you fill them out. Therefore, one thing we need to remember: templated functions and classes don't actually exist until you use them! A solution is: a header file including template declarations also constains their definitions. However, this seems to violate the rule of the separation of the declaration and definition.

Reference:
[1] http://www.informit.com/guides/content.asp?g=cplusplus&seqNum=298&rl=1

Sunday, April 15, 2007

Cooperative Diversity for Wireless Networks

Cooperative diversity can emmulate an antenna array and then exploit spatial diversity in wireless networks with fading channels. It exploits the broadcast nature of the wireless medium and allows radios to jointly transmit information through relaying.

Traditionally, in ad hoc networks, packets are forwarded from the source to the destination through multi hops serially. The well-known capacity of wireless networks obtained by Gupta and Kumar in 2000 is with this strategy. By using Cooperative diversity, the source and the relay nodes may cooperate together for data transmission. The capacity of this kind of network has been investigated by Xie and Kumar.

The use of cooperative diversity is manifold:
1) Increase capacity (enlarge capacity region)
2) Improve reliability in terms of diversity gain
3) Diversity-multiplexing tradeoff

Different algorithms can be applied for cooperative communication, some examples are:

1) Amplify-and-Forward
In this case, relays just simply amplify the received signal with a linear transformation.
2) Decode-and-Forward
Relays first detect and decode the received signals and then re-encode them. This decoding and re-encoding procedure can be considered as a non-linear transformation.
3) Selection and dynamic relaying
In this case, cooperative terminals adapt their transmission format according to the measured channel state information.
4) Incremental relaying
This scheme exploits limited feedback from the destination terminal for relaying.

Incorporating the cooperative diversity into the network is still an open problem.

Reference:
[1] J. Nicholas Laneman, "Cooperative diversity: models, algorithms and architectures," Cooperation in wireless networks, Springer, 2006

Wednesday, April 11, 2007

Adaptive modulation v.s. High order diversity

Today's learning: adaptive modulation may become unnecessary as the diversity order is increased. It can be viewed as a lower-complexity alternative to diversity technologies, such as MIMO.

Remember, adaptive modulation or diversity only offers advantages over fading channels. Adaptive modulation can employ high-order modulation schemes to adapt to the channel state and then increase the system throughput. Diversity utilizes the independent property between two or more links. When only one receiver is provided, adaptive modulation can be employed. But when more than two receivers are available, it is better to use diveristy technologies.