### Archive

Archive for April, 2010

## Weekly Update 30 Apr 2010

Last week I set out the following plan for the week:

For the next week I plan to nail down how I can implement vector clocks for location and proximity, also think about what metrics we can derive from this. At the same time I plan to read through Knox’s thesis, and read Simons paper, and try to formalise my ideas about location.

Since then, I have read Simon’s paper, which provided a nice discussion about what needs to be thought about when we deal with location. I have made progress with the simulator software. I also wrote code to process all of the data I collected from N95s, so that each reading in the database has a location associated with it. The simulator will now be able to use this to drive the location aspects of nodes.

I had some thoughts about planning a chapter about deriving location from sensor readings (e.g. WiFi position, GPS Readings, Cell Tower Positioning and Triangulation) – e.g. how can we measure the accuracy of our posistion calculations, how accurate does a the position need to be, and how should we represent location.

I also started to read up on Graph Theory, but starting with Barabasi’s book ‘Linked’ , which gives a really interesting overview of Graph Theory and how to measure aspects of complex networks. This made me realise that I will also need a chapter about this subject, and so I plan to write a review of Graph Theory based roughly based on this book.

I have also been giving more thought regarding Vector Clocks and how to use them, but I have not implemented anything yet.

My plan for next week is:

• to get a better understanding of Graph Theory by finishing the book.
• Implement vector clock code in the simulator, based on proximity, and work towards a location based one.
• Formalise my thoughts on how to use Vector Clocks of proximity and location, and what metrics can be derived from them
• Generate a rough outline of chapters for my thesis, and identify the main areas for the background section
Categories:

## weekly report 16 Apr 2010

April 16th, 2010 1 comment

This is the first weekly report to Paddy.

Since our meeting on Wednesday, there is not much for me to report, however as this is the first report, I will summarise what the short term plan for the next few weeks is.

At our meeting we discussed my ideas about where my PhD will focus, which I documented here, the actions I identified from the meeting are as follows:

• Refine contributions section – (this will come with time as the project progresses)
• Refine and tighten up the hypothesis section – remove negative items
• Beware of going down unneccasary rabbit holes – don’t get distracted
• Nail down what each main part is
• using  vector clocks to derive metrics,
• predicting mobility and proximity,
• exploring the value of distance to other nodes (e.g. is 3 hops enough?)
• how to bring it all together
• Dig out reviews on DTN’s- especially about patterns and finding important nodes
• Make some enquiries about datasets
• Email: GW, Barry Smith, Aaron, Knox
• Intel Placelab
• Think about the meaning of location (Read Simons paper: Where’s Waldo)
• Complexity of data
• What data can we store in vector clocks
• Using Barabasi’s prediction approach to generate traces
• Mechanisms for discovering best next hop
• individuals only calculate their own ability to deliver
• individuals ask other nodes if they can deliver
• combination of different approaches depending on who we are trying to contact (e.g. friend, vs friend of a friend, vs everyone else)
• Consider complexity analysis

Since the meeting I have started to reconsider the hypothesis questions as follows:

1. Human mobility patterns are predictable
2. Human proximity patterns are predictable
3. Knowledge of proximity and location makes opportunistic routing more efficient than proximity alone.
4. There are low complexity algorithms based on vector clocks that can be used for routing
5. Any given node will only need to communicate with with other nodes that they know of

For the next week I plan to nail down how I can implement vector clocks for location and proximity, also think about what metrics we can derive from this. At the same time I plan to read through Knox’s thesis, and read Simons paper, and try to formalise my ideas about location.

Categories: weekly report

## Supervisor PhD Meeting 14 Apr 2010

This was the basis of my Pitch_to_Paddy

Mobility is NOT location…. see Simons paper

### Discussed my ‘Hypothesis’

• Human mobility patterns are predictable
• Human proximity patterns are predictable
• Knowledge of proximity and location makes opportunistic routing more efficient than proximity alone.
• Proximity and Mobility can be used independantly to achieve the same efficiency in oppotunistic networking.
• Mobility or Proximity can be discounted when planning opportunistic networking algorithms.
• There are low complexity algorithms based on vector clocks that can be used for routing
• Any given node will only need to communicate with with other nodes that they know (friends), or want to know (friends of friends).
• Paddy suggested this might be a bit like a DNS tree, which hands off knowledge
• Also experiments need to establish that a friend or a friends of a friends knowledge is enough to route
• Might establish that 3 degrees is more than enouhg
• tradeoff = you can get better efficiency if you give more coverage of the network

### Local Metrics

Using vector clocks –

Range – how many hops away – build a knowledge about the network using information in the vector clocks – how do you do that? This is a PhD part.

How do we determine the important nodes? – the Aaron Quigley effect.

Nodes in your ball of radius = sphere of interest = friends, +1 hop = friends of friends, +1 = everyone else.

Dig out reviews on DTN’s – especially patterns  – but paddy thinks that the notion of location and proximity have never been used, but the patterning structures e.g. highly important update nodes.  So i need to look at ways of discovering special nodes. How do they determine that . Location thing seems to be different- find a review.

Mobility as opposed to location – gives your prediction element.

Limit the range of forward projection.

### Datasets

Email GW to see if he can get a public dataset. – sign over under NDA?

Email Barry Smith to see if he knows of any datasets we can use. – Vodaphone dataset?

Email Aaron Quigley – he will know if there is any publicly available – his masters student has access to a corporate travel dataset.

Also – see Simons Paper about location.

Look up Intel Placelab dataset

Email knox to see what datasets he might have.

## Progression

Paddy not sure where the Vector clocks fit in

Is it a novel implemenation mech. – i.e. am I going to use vector clocks in this thing.

I want to make a prototype. – paddy likes the idea – there are some hard questions – some novelty in there. This parts Understanding how to frame solid hypothesis. reading reviews. building exp structure, breaking out a few bits – vector clocks, heuristics about making decisions, how it all fits together.

Not fully formed so need to think a bit more about it

### Future

We can turn the VC thing on its head, and make it useful for proximity and location.

I want to build prototype

Need to be careful not to spend too much time comparing to existing things if they are not really related.

Important thing is does it matter where you are when I pass you a message  – as proximity and mobility are the same – do I pass it to you because i know you see that person, or because I know you will be in the same location as that person.

Nodes can predict their own positions – share this information with other nodes – paddy suggested sharing based on the types of people – e.g. friends get detailed info, FOAF get  obfuscated location, others get much broader information.

### Requests?

Does a node do calculations about other nodes, or does it ask the other node – can you get this to this person?

A little but like Agent systems?

You might have different approaches depending on who you are dealing with – e.g. message to a friends goes through friends, message to FOAF goes otherwise, everyone else – can you get it to somewhere nearer than me – or somehting…

Then we can say we of course can encrypt this information.

### Plan

Paddy felt that vector clocks etc. that are used to encode e.g. double vecotr cocoks location mobility, is a solid piece of work, and if it gets into a good conference, then it is my PhD.

It will need a Order of computaion section with a complexity analysis i.e. is it N^N, Nlog(N), N^2, N^3 – dont go much beyond that  – need to analyse the algorithms at the end. well travelled ground about what the complexity of vector clocks is.

I want to Nail down what these metrics in the system are, then implement CAR using these metrics as well as coming up with my own algorithm.

Need to convince Paddy what algorithms/datasets to compare with, there needs to be a good rationale be behind it.

Need to refine the contributions bit – but this will come with time

Hypotheis section is  good – but must refine and remove negative ones – it should keep the positive ones, and prove one thing true or false – pick the one we think is most likely.

Add another hypothesis that low complexity algorithms based on vecotr clocks (30:24)  can be used.

Dont go down rabbit holes!!! Give Paddy weekly updates – every Friday – nag paddy – if he has not  responded by 10am monday – Paddy will comment back

Tighten up – look at knox Hyp section. – and write a halfpage hypothesis introduction and a one/two line hypothesis at the end.

#### Aside:

Can we use Barabasi way to generate new dataset – almost reverse engineer their preditions, and try to get a dataset based on it?

e.g. Random graph of streets for dublin, randomly place nodes – simulator and start to make locations as the predictions.

Dig out reviews on DTN’