Feeds:
Posts
Comments

Archive for the ‘Technology Basics’ Category

An Introduction to GIS

The motivation for this post is simply the growing importance of Location-Based Services (LBS) in the mobile environment. To provide such services knowledge of location and topography is needed. Services will also benefit from knowing the proximity to complementary services, routes and obstacles. All such information come from GIS. If someone – as a developer or provider – is attempting to get into LBS space, it is vital to understand GIS first. This post is a brief introduction to GIS as I have understood it. I am by no means an expert in this area and readers may wish to do further research on their own. Feel free to add your comments to this post.

Definition
There are two definitions of GIS – Geographical Information System and Geographical Information Science. As a system, the focus is on methods and processes. It relates to tools, software and hardware. It defines how data is input, stored, analyzed and displayed. As a science, it deals with the theory behind the system. It asks and answers why something should be done in a certain way. It looks for solutions to technical and theoretical problems. It challenges existing methodologies and models. For example, as a system there may a defined way for data transformation but as a science justifications are needed why such a transformation is correct and applicable.

Historically, there has been no consensus within the fraternity but it is being increasingly felt that GIS is both a science and a system. One cannot survive without the other and both have their place. More than this, the understanding and use of GIS has evolved over time. In the early days it was no more than an automated mapping system. It meant the use of computers to make maps in a cost-effective manner. Perceptions changed quickly as people realized that more can be gleaned from maps than the information available from map data. Visualization brought new possibilities and the idea of spatial analysis was born. Such spatial analysis described how data is to be combined, what questions need to be asked for specific problems and what solutions could be sought by means of spatial relationships. The human eye and the brain can perceive patterns that are not obvious from data described as tables and spreadsheets.

As data became pervasive, the quantitative revolution came to the fore. Number crunching or data intensive processing as they came to known in computing lingo became popular. GIS may not have given impetus to quantitative analysis but it surely made it important. In turn, GIS rode on improvements that happened to quantitative analysis. Nonetheless, students studying GIS are sometimes blamed for seeing GIS as nothing more than quantitative analysis. The fact is that qualitative analysis is an important aspect of GIS. This is what separates the notions of system and science. Intuition and spatial analysis are still the primary drivers for GIS. GIS research is much more than just numbers and quantitative analysis. Figure 1 gives a snapshot of the breadth of analysis that happens in GIS [1].

Figure 1: Content analysis of GIS journals
from 1995-2001 (based on 566 papers)
GIS Research

Applications
At this point it would be apt to know the applications that use GIS. The real value for most people is not GIS itself, but rather how and where it is used. It has already been mentioned that in the domain of mobile communications, GIS enables LBS. Traditionally, it used to be used only within geography – to identify, record or classify urban areas, rural areas, forest cover, soil type, course of rivers, to mention a few. These days it is used in many other fields. It can be used by city planners to aid decision making. For example, what’s the best route to lay a road between two points through an urban landscape without going underground? GIS can give answer to such a question. GIS can help in social analysis. If women in a certain area have a higher incidence of breast cancer, GIS data of various contributing factors can be combined and analyzed to arrive at an answer or a set of possible answers. For transportation and service delivery, GIS is an important tool to plan routes, profile markets and determine pricing models. E-governance uses GIS for property survey lines and tax assessments.

I will give an example of where GIS could be useful with reference to Tesco stores in the UK. I noted consistently that Tesco stocks a variety of Indian consumer products in outlets that are close to Indian communities. Two Tesco outlets in different locations often have quite different items. I don’t know how this happened but my guess is that Tesco learnt by experience. Sometimes this intelligent differentiation is missing in outlets. However, if GIS had been used, such stores could stock goods focused to ethic community groups from the outset. There is no learning period needed. Provided decision makers ask the right questions and know how best to use GIS data, Tesco could predict consumer behaviour patterns in a specific area even before it has opened its outlet there.

Approaches and Identities
It will be apparent from the diversity of applications that GIS does not mean the same thing to two people. Cartographers, sociologists, city planners, environmentalists, geologists and scientists, could all potentially look at GIS differently. Let us take the example of mapping a forest area. Wildlife enthusiasts would map the forest cover with emphasis on habitat and conservation. They would consider how much light reaches the forest floor for the undergrowth to survive. On the other hand, forest officials more concerned with the health of trees would focus on height and width of trees. They would consider different types of trees and forest canopy. If it is a commercial forest, loggers would be more concerned with factors associated with their business.

The point about GIS is that data is just a representation of reality. The same reality can be seen differently by different people and they all can be true at the same time. This is somewhat like painting. Two painters can see the same scene in quite different ways. It is said that painting is all about making choices – what details to include, what to leave out and what to emphasize. No one painted olive trees like Van Gogh yet his trees are every bit as real as the post-Romantic Realism of Courbet.

The terms used to describe this are epistemology and ontology. Epistemology is the perspective through which reality is seen. It is sort of a lens that notices some things and filters out the rest. Ontology is refers to the reality. They exist on their own but they are interpreted through epistemology. The reality one sees could be different from another simply because their perspectives are different. Without going into details, different epistemologies have been discussed in literature – social constructivism, positivism, realism, pragmatism. For example, positivism believes in observations that can be repeated before deriving a theory out of it. Realism emphasizes more on specific conditions and particular events. Ultimately, these approaches straddle the divide between GIS being a system and a science.

Governments for example may apply a certain epistemology to suit their purpose. The resulting ontology may not necessarily be the way people see themselves. Thus, Public Participation in GIS (PPGIS) has become important for communities to challenge governments by defining ontologies that they believe is real or at least more real.

For computers, ontology is simply the way data is stored, objects are represented or object relationships are described. For example, a bridge across a road can be underground or above the road. Such relationships are defined and this represents reality for a computer. Data is not everything but they are a key component of GIS.

Handling Data
This is a complex area in itself. There is data collection, classification, interpretation and representation. Broadly, there is raster data and vector data. With raster data, geographical area is divided into units or cells and attributes are set for each of these units. Raster data can be easily transformed and combined. Handling raster data is simple. This is not the case with vector data in which the basic components are points, lines and polygons. A geographical area is described from these components. Both these are means to describe an entire area without any gaps. Generally these are called field models or layer models. There are also object models in which objects are represented within an area but the area in its entirety has not been mapped. Thus object models may have many gaps which may not be significant for the purpose for which these maps have been generated.

Scaling of data is regarded as a difficult activity that involves lots of decision making. At 1:25000 roads, bridges and towers may be clear in an urban area. At 1:75000 such fine details may be lost. The problem is how to aggregate data, classify them correctly and represent them at the scale of 1:75000. It all depends on the context. If a contractor tasked to maintain bridges is looking at such a map, he should probably see bridges even at the scale of 1:75000.

Data collection for a specific purpose is an expensive job. Thus it becomes necessary to share and combine data from multiple sources. The problem with combining data is that each source has collected it for a specific purpose. One source collecting tree data may classify all trees taller than 50 meters as tall. Another source may use a different criterion. If the actual height has not been recorded it becomes difficult to combine the two sets of data and come up with a consistent ontology of tall trees in a forest area. On the flip side, different data sets may be representing the same objects but may use different terminology. For example, a “limited access road” in one set may be same as a “secondary road” in another set. Only with the help of local knowledge we would realize that they are talking about the same roads. Then, the two data sets can be usefully combined. Data semantics varies and it needs to be understood well to make the best use of data. We ought to realize that data offer particular points of view, not an absolute reality. In this context, primary data is one that is collected for a specific purpose. Secondary data is one that is used in GIS but was collected for a different purpose.

Attempt has been made to standardize data so that data can be merged more consistently. Metadata is used to facilitate this. Metadata are descriptors of data. They record how data was collected, when it was collected, at what scale is it applicable, what classification was used and many other things. Metadata is a good step forward but it does not entirely solve the problem of dissimilar data collected differently for different purposes. With metadata, we at least have more information about available data so that we can use them as appropriate. This is really a critical part of GIS these days as data is shared widely. Combining data without understanding the science behind it could lead to inaccurate analysis that builds a conclusion divergent from reality.

Modelling and Analysis
With so much data available, models help us build a picture of the world and its realities. Analysis follows as a necessary step in understanding this reality. Overlay technique and analysis is a fundamental approach. An area can be seen from the perspective of many layers, each of which is overlaid on top of another. Bringing together spatially different data sets can assist in solving problems and answering questions. Schuurman [1] quotes the example of identifying population areas that are at risk of fires in Southern California. Population is on one layer. Rivers which help break the spread of fires in on another layer. Road networks is on another layer that relate to accessibility and user location. Tree or forest cover is yet another layer that relates to spread of fires. This can get further complicated if we bring in local weather patterns and wind directions on another layer. Overlay technique is easily done with raster data but much more complex with polygon data. For computation, overlay uses set theory.

Another example is environmental modelling that could be useful for studying levels of pollution and areas at risk. Air emission is modelled. Noise is modelled. These models are based on factors which might be available as GIS data. Contours from these models are generated to highlight patterns of noise or air pollution. These are then converted into GIS data. The next step is to overlay all this GIS data and visualize the overall impact on the environment in a particular area. Such use of GIS helps in decision making. Thus, GIS today combines visualization as well as quantitative approaches to problem solving.

Decision making exists even in the process of using GIS data. Often many areas are incompletely mapped while others may be complete. Representing all the data on a single map is inaccurate. Thus decision has to be made to bring all data to a common platform of comparison. Data reduction enables one to do this. Likewise, a project attempting to model and analyze something with an accuracy of 50 meters may not be possible for reasons of privacy. One example of this is when working with individual health data. Some process of data averging over a wider area must be used. Spatial boundary definitions present their own problems. GIS likes crisp boundaries but this is never achievable in reality. Scales are different. Classification criteria are different. National data is collected for a different purpose at a different scale than taluk data. Combining the two is not exactly a trivial job. This is named the modifiable area unit problem (MAUP). MAUP deals with aggregation of data from different scales or redrawing of the same map at a different scale.

Conclusion
GIS is an interesting field that has many practical uses. It is more than just data collected for a particular location. It is a science. It is a system. In a future post, I will look at the use of GIS specifically for LBS. From what I have learnt of GIS, a truly powerful LBS application will do a lot more than just feeding users with data based on their location.

References

  1. Nadine Schuurman, GIS: A Short Introduction, Blackwell Publishing, 2004.

Read Full Post »

Just two weeks ago Zahid Ghadialy uploaded a post on Carrier Ethernet Transport (CET). It was a basic introduction which had to be supplemented by my own research to understand what CET actually meant. Part of the difficulty is the “collision” of terms. For example, the interview of a Nokia-Siemens manager mentions the term “transport layer”. This can be confusing if it is taken in relation to the OSI model. Transport layer within the context of CET is quite different from the transport layer that is TCP or UDP. We will revisit this later.

So what is CET and how does it fit into the world of mobile and wireless? Meriton Networks defines CET as,

an architectural approach for building scalable transport infrastructure for supporting Ethernet and the evolution to NGNs.

This is a good definition because we can learn much about CET from the definition alone. The following points can be made:

  1. CET is not Ethernet itself but an architecture that enables wide scale deployment of Ethernet from its so far traditional use.
  2. Current transport networks are somehow not scalable and CET with the use of Ethernet can provide that scalability.
  3. NGNs require QoS support, high bandwidth, transport efficiency and scalability. These can be met with CET.

I got interested in CET because of a recent press release from India’s cellular market leader Airtel [Shockingly Fast Broadband]. The article claims that Airtel can now provide 8 Mbps broadband to its customers, the first provider in India to reach such a high bandwidth. Their transport architecture that makes this possible is CET which has been deployed in Bangalore, Chennai and Delhi. In other areas, CET will be introduced slowly. Meanwhile SDH has been upgraded to support 8 Mbps. Airtel claims that its infrastructure is now IPTV ready.

Ethernet is defined in IEEE 802.3 and relates to Data Link layer of the OSI model. The physical media can be anything. Traditionally, coaxial cables were used. Today, most networks use twisted pairs. Those with high bandwidth requirements such as Gigabit Ethernet may use optical fibres. Ethernet has been used in LANs widely but it do not scale to MANs and WANs. For example, spanning trees do not scale to large networks. Thus Ethernet have rarely been considered for carrier transport. Moreover, SONET has consistently offered higher bandwith than Ethernet and sub-50 ms resilience, so that most transport networks today use SDH/SONET architecture. In a wireless environment, data link layers are usually different and do not conform to the IEEE 802.3 Mac data frame format.

The advantage that Ethernet brings is its ease of implementation and low-cost when compared to SONET. Ethernet is essentially a connection-less protocol. It enables multiple access but has no functionality for providing QoS. Yet CET is attempting to get more out of Ethernet by using it with other technologies/layers.

There was a time when end-to-end packet service was essentially connection-less using IP. Routing was performed at IP (Layer 3). With MPLS, label switching was done (Layer 2). MPLS introduced a connection-oriented virtual paths based on labels. This enabled traffic engineering and QoS provisioning. It was widely deployed in transport networks. With the higher bandwith requirements and greater flexibility demanded by NGNs, this task is being pushed from Layer 2 to Layer 1. Ethernet enables a simple and uniform interface while the underlying transport could be any suitable physical layer that has some switching functions as well. CET, for the sake of system performance, blurs some of the traditional boundaries between layers as defined in the OSI model.

Ethernet data frames can be carried across the transport network. Switching is likely to happen at the optical domain. Wavelength switching, sub-wavelength switching or Ethernet tunnel switching are possible. Using just enough Layer 2 functionality at the optical layer, CET enables a clear separation between service layer and transport layer. The latter refers to the mechanism by which data is transported within the network. It does not refer to the transport layer of OSI model. Switching happens within the transport layer. Carriers can concentrate on their services rather than the transport mechanisms because these two are no longer closely coupled. This is represented in Figure 1 (from Meriton Networks).

Figure 1: CET Separation of Service and Transport Layer
CET Service and Transport Layers

Issues of scalability and QoS are addressed using Provider Backbone Bridging with Traffic Engineering (often called Provider Backbone Transport) PBB-TE/PBT. Spanning trees have been replaced with GMPLS to create bridging tables. It will be apparent from these considerations that Carrier Ethernet is a lot more than just Ethernet. Carrier Ethernet is defined in relation to services on provider networks. It is partly about the transport infrastructure but also about the service delivery aspects. Thus, we have two key aspects of Carrier Ethernet – Carrier Ethernet Service and Carrier Ethernet Solution/Transport.

Many organizations are involved in the standardization of Carrier Ethernet (IEEE, IETF, ITU, MEF). Among these Metro Ethernet Forum (MEF) is the primary organization. The standard is by no means complete. Carrier Ethernet is the future and it is still in its infancy.

For further reading:

  1. Tom Nolle’s Blog
  2. Comparing Alternative Approaches for Ethernet-Optical Transport Networks
  3. Ethernet Technologies, Cisco documentation.
  4. Abdul Kasim, Delivering Carrier Ethernet: Extending Ethernet Beyond the LAN, McGrawHill, 2007.

Read Full Post »

Yesterday I visited a bookshop on Bangalore’s M.G. Road. I came across this classic – John G. Proakis, Digital Communitations, Fourth Edition, McGraw-Hill, 2001. I was overcome with a wave of nostalgia. This is a book I had used in engineering course in college some twelve years ago. I must have used the second edition. As a student, with limited financial resources, I had never bought a single technical book. The library supplied all that I needed. But yesterday I bought my first technical book. At $10.50, it was cheap by international standards and reasonably priced for India.

It has been many years since I read a book like this. The equations looked alien to me. I could not recognize the Fourier Transform. The complementary error function erfc(x) meant something but I had only a vague idea of its definition. The famous theorems of Shannon were somehow familiar but still a distant memory. Nonetheless, it was exciting to get back to the basics of digital communications.

In this post, I shall try to touch upon three things from this book and look at their relevance from the perspective of GSM/UMTS.

Noisy Channel Coding Theorem

This theorem from Shannon is stated as [1]:

There exist channel codes (and decoders) that make it possible to achieve reliable communication, with as small an error probability as desired, if the transmission rate R < C, where C is the channel capacity. If R > C, it is not possible to make the probability of error tend toward zero with any code.

A related equation to this defines the upper bound for the capacity C of a band-limited AWGN channel whose input is band-limited and power-limited [1]:

C = W log2 (1 + Pav/WNo) where

Pav is the average signal power
W is the signal bandwidth
No is the noise power spectral density

So for higher normalized capacity C/W (bits/s/Hz), power has to increase. So if we increase the modulation from QPSK to 16QAM as in HSDPA we get a higher normalized capacity. At the same time, we tighten the constellation if we keep the average signal power the same. A tighter constellation leads to higher BER. To obtain the same BER, we need to increase signal power. So although 16QAM gives us higher bit rate, this must be accompanied by higher power as indicated by the capacity formula. Another way to look at the same thing is to say that by moving to 16QAM we have more bits per symbol. Given that the energy per bit is the same, we require more power. This is understood by the following equation:

Pav/WNo = (Eb/No)(C/W) by substituting EbC for Pav.

On the other hand, for a fixed power, only an increase in bandwidth will give us higher capacity. This is true if we compare GSM against UMTS. The former has a bandwidth of only 200 kHz while the latter has one of 5 MHz.

A comparison of Shannon’s limit against the performance achieved by some standards is given in Figure 1 [2]. We can note that HSDPA is within 3 dB of the limit which is pretty good. We must remember that Shannon’s limit is for an AWGN channel, not for a fading channel (slow or fast). Yet fading characteristics can only make the performance worse, so that Shannon’s limit is still a definite upper bound on capacity. The fact that HSDPA can come within 3 dB of the limit is a tribute to advance receiver techniques. The Rake receiver is a key element in UMTS that makes the best of multipath diversity. Likewise, fast power control mitigates fades and improves BER performance. Without fast power control, the average SNR would be significantly higher to maintain the same BER.

Figure 1: Performance Relative to Shannon’s Limit
Performance against Shannon Limit

In a future post, I will look at MIMO in relation to Shannon’s limit.

Channel Coherence Bandwith

In a multipath channel, delayed versions of the signal arrive at the receiver with different delays, amplitudes and phases. A multipath intensity profile is the delay power spectrum of the channel in which most of the signal power arrives together with low delay and tapers off towards higher delay. The range of values over which this profile is non-zero is called the multipath spread or delay spread (Tm) of the channel. In practice, a certain percentage may be used to define the multipath spread, i.e. 95% of total power is within the multipath spread. In the frequency domain this can be shown to be related to coherence bandwith (Δf)c as

(Δf)c = 1/Tm

What this means is two frequencies separated by the coherence bandwith will fade differently through the channel. If a signal’s transmission bandwith is less than this amount, the channel is said to be frequency-nonselective or frequency flat. Otherwise, it is frequency-selective.

Multipath varies greatly in relation to the terrain. Table 1 prepared by the Institute of Technology Zurich is a nice summary of the range of values that multipath spread can take.

Table 1: Delay Spread for Different Terrains
Delay Spread Values

Apparent from this table are:

  • Urban areas have a smaller delay spread as compared to rural.
  • Indoor environments have small delay spreads.
  • Where there is a significant LOS path, delay spread is less.
  • There is some variability due to carrier frequencies and bandwith. In general, the terrain determines the delay spread.

Let us take 3 µs as the delay spread for an urban area. The coherence bandwidth would be 333 kHz. This is more than 200 kHz bandwith of GSM. Thus, this environment is frequency-flat for GSM. For WCDMA, the coherence bandwith is much smaller than 5 MHz. This is an important reason why WCDMA is called “wideband”. The channel is frequency-selective. Rake receivers are therefore quite important for WCDMA to reconstruct the signal without distortion.

For GSM, the fact that the channel is frequency-flat is used to good advantage. In other words, if the channel fades at one frequency it may not at another that’s at least one coherence bandwidth away. GSM employs frequency hopping which gives an improvement of 2-3 dB. On the other hand, if we consider a rural environment with delay spread of 0.03 µs, the coherence bandwith is 33 MHz which is quite high. GSM does not have frequencies spread over such a wide band. Thus frequency hopping is not likely to improve performance in such an environment, at least on this aspect. But frequency hopping does more than combat slow fading. It also mitigates interference which is why it is still useful when the delay spread is low.

Channel Coherence Time

For this we need to consider the time variations of the channel which is seen as a Doppler spread. Let us say that Sc(λ) is the power spectrum of the signal as a function of the Doppler frequency λ. The range over which this spectrum is non-zero is the Doppler spread Bd. Now we can define the coherence time (Δt)c as

(Δt)c = 1/Bd = co/fv where

co is the speed of light
f is the carrier frequency
v is the velocity of the receiver

A slowly changing channel has a large coherence time and a small Doppler spread. For example, in WCDMA if we consider a carrier frequency of 2 GHz, a vehicular speed of 250 kph, we get a coherence time of about 2.2 ms. This is smaller than UMTS 10 ms frame. Thus channel characteristics do change within a frame. This means that a UMTS frame experiences fast fading. How does the design combat fast fading? It does it simply by dividing the frame into 15 slots. Transmission power can be adjusted from one slot to the next. TPC bits sent in each frame enable this fast power control. Thus fast power control at the rate of 1.5 kHz help in combating fast fading. The net effect of this is that at the receiver, the required dBm is maintained to meet the target BLER set by outer loop power control.

In GSM, the same calculation yields a coherence time of 4.8 ms which is much larger than a GSM slot (0.577 ms). So GSM experiences slow fading. For GPRS on the other hand, multiple slots can be assigned to the MS. A frame is about 4.6 ms. So GPRS is on the border of slow to fast fading. This is tackled by transmitting an RLC/MAC block in four bursts over four frames.

Figure 2 is a representation of the time and frequency selective characteristics of a channel [4].

Figure 2: Time-and-Frequency Selective Channel
Time and Freq Selective Channel

References:

  1. John G. Proakis, Digital Communitations, Fourth Edition, McGraw-Hill, 2001.
  2. Data Capabilities: GPRS to HSDPA and Beyond, Rysavy Research, 3G Americas, Sept 2005.
  3. Prof. Dr. H. Bölcskei, Physical Layer Parameters of Common Wireless Systems, Fundamentals ofWireless Communications, May 3, 2006.
  4. Klaus Witrisal, Mobile Radio Systems – Small-Scale Channel Modeling, Graz University of Technology, Nov 20, 2007.

Read Full Post »

« Newer Posts