Matt Stabeler

In my last update, I identified the following tasks:

Finish worked example of interaction network using vector clocks

Plan short experiment to collect ground truth location data

Finishing Barabasi’s book.

Prepare to show Paddy the finished worked example, picking out interesting parts and identifying next steps

other tasks

• Implement vector clock code in the simulator, based on proximity, and work towards a location based one.
• Read Knox’s thesis.
• Generate a rough outline of chapters for my thesis, and identify the main areas for the background section
• Write down ideas about how to define locations (draft)
• Dig out reviews on DTN’s- especially about patterns and finding important nodes
• Find out about funding from September 2010, (IRCSET, CSI, Lero, more?)

Since then, if I am honest, I haven’t achieved much, partly due to my being useless at time management, and due to various commitments that required more time than I thought, and in hindsight I should have avoided (Demonstrating, ODCSSS, Computer Science Summer School, visiting family, buying a car) my plans have gone out of the window. I am also obliged to give up more time this week (CSSS, Tues 2 hours, Wed 5 hours, Thurs and Friday 8 hours each!) which I would rather have avoided.

I really want to get up to speed, and I am very conscious of the little amount of time I have left, so after my commitments this week, I will dedicate all of my time to my PhD work, and will endeavour to get my work back on track. But in order to do so, I need to have a clear path to completion, so I propose the following tasks:

Overview Tasks

• Meet with Paddy to discuss a plan for completion
• Investigate options for continued funding

Project specific tasks

• Plan short experiment to collect ground truth location data
• Prepare to show Paddy the finished vector clock implementation (workthrough), picking out interesting parts and identifying next steps
• Summarise findings from vector clock implementation (workthrough)

Other tasks

• Implement vector clocks in simulator, based on location
• Read Knox’s thesis.
• Read Barabasi’s book.
• Generate a rough outline of chapters for my thesis, and identify the main areas for the background section
• Write down ideas about how to define locations (draft)
• Dig out reviews on DTN’s- especially about patterns and finding important nodes (any suggestions would be appreciated!)

And in context, my conflicting obligations and plans etc. are as follows

• Computer Science Summer School – w/e 13 June  (23 hours!)
• ODCSSS Student  – until w/c 9 August
• Planned trip (home 1week,  Germany 1 week) – Fri, 30 July – Sun, 15 August

Last week I set the following tasks:

Continue/Finish worked example of interaction network using vector clocks

Plan short experiment as above (or at least think about whether it would be useful)

Get a better understanding of Graph Theory by finishing Barabasi’s book.

Make some enquiries about datasets

and

Implement vector clock code in the simulator, based on proximity, and work towards a location based one.

Read Knox’s thesis.

Generate a rough outline of chapters for my thesis, and identify the main areas for the background section

Write down ideas about how to define locations (draft)

Dig out reviews on DTN’s- especially about patterns and finding important nodes

Find out about funding from September 2010, (IRCSET, CSI, Lero, more?)

I have got a good way through doing a worked example; I have created 6 characters (based on real people) and have given them home, work, and leisure locations. I have created a notation for recording movement events, and have generated skeleton location graphs for all individuals. I have started to generate the characters daily movements.

I have given a little more thought about planning the experiment suggested in my previous post, and have identified some participants (the same ones I based the workthrough on), and I believe collecting this information will be useful to get a good idea for people’s real movements.

The following week is a busy one for me, as I have to demonstrate (Monday 3 hours), attend and mark presentations for the HDIP class on Wednesday (all day) and on Friday I am visiting family in the UK (volcanoes permitting). After this I have very few demonstrating responsibilities. So the following is my plan for then next two weeks.

• Finish worked example of interaction network using vector clocks
• Plan short experiment to collect ground truth location data
• Finishing Barabasi’s book.
• Prepare to show Paddy the finished worked example, picking out interesting parts and identifying next steps

other tasks

• Implement vector clock code in the simulator, based on proximity, and work towards a location based one.
• Read Knox’s thesis.
• Generate a rough outline of chapters for my thesis, and identify the main areas for the background section
• Write down ideas about how to define locations (draft)
• Dig out reviews on DTN’s- especially about patterns and finding important nodes
• Find out about funding from September 2010, (IRCSET, CSI, Lero, more?)

In last week’s update I said that I intended to do the following:

• 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.
• Read Knox’s thesis.
• 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

Since then, I had a quick chat with Paddy, and we discussed simplifying what I should work on,  and came up with a plan to create an example work through of interactions and locations.

Before that, I had started a rough plan of network of interactions within a ficticous network, I also continued to work on the simulator software, and had generated latitude longitude pairs for every reading in the database (479,148 in total).

Since our meeting, I concentrated on working up an example workthough, and for this week I plan to continue this.

I also thought about a small and easy experiment to test the validity of what I was generating; ask some volunteers to:

1. Write down their movement for the last week, and identify the locations they considered to be most common.
2. Write down their predicted locations for the next week.
3. Ask them to keep a record of their actual locations over the next week.

This could conceivably be done very easily in written notebook form, or slightly more challenging – as an online system. This will allow us to get a better idea of what peoples real movements are, and see if it looks like the workthrough we have generated.

My plans for this week are as follows:

• Continue/Finish worked example of interaction network using vector clocks
• Plan short experiment as above (or at least think about whether it would be useful)
• Get a better understanding of Graph Theory by finishing Barabasi’s book.
• Make some enquiries about datasets

(note – Laura is coming home this week)

Other tasks to keep in mind:

• Implement vector clock code in the simulator, based on proximity, and work towards a location based one.
• Read Knox’s thesis.
• Generate a rough outline of chapters for my thesis, and identify the main areas for the background section
• Write down ideas about how to define locations (draft)
• Dig out reviews on DTN’s- especially about patterns and finding important nodes
• Find out about funding from September 2010, (IRCSET, CSI, Lero, more?)

Met with paddy in his office and discussed updates so far.

Paddy wants to see something tangible by next week’s update – i.e. a worked example of how vector clocks will work in terms of location.

Also emphasised that I should not get sidetracked! (of course!)

Suggested storing temporal  information (parallel vector clocks?) – e.g. a from to, so that we can say things like does this time overlap this one, is it contained withing etc. etc.

Also thought about how to define location – the bounding of the location  gives an experimentation thing – change the grid size – whats the computation impact of the size of the grid – and what the relevance e.g. too big and it makes realistic.

Construct vector stamps – 5 separate path across these locations, two or three allow drop messages – run through and pick various vector clocks at various times, and show them. Then start generalising them.

From this we can draw general things about e.g.: decisions made, what information is stored, what we put in vector clocks, what operators we need.

Then run a simulation and see if generalisation works. Then we can see if some things fall down, and come back and change things.

Should stick with ideas about location, not proximity yet.

Using this it is then possible to write this concisely.

Actions:

• Generate a worked example/scenario
  • show examples of vector clocks at times
  • show the movements over time
• Don’t get sidetracked!

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.
• Read Knox’s thesis.
• 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

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)
• Start with prototype to explore the following:
  • Complexity of data
  • What data can we store in vector clocks
• Things to think about:
  • 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.

Had a meeting with Paddy for me to pitch my ideas.

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.

Ideas about locations

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.

Met with Paddy,

Talked about the possibility of needing to get a new supervisor, and Paddy said that IF he does leave to Tazmania, then we will have to think about who could be the best person for the job. We thought that if I do finish up at Christmas 2010, then perhaps I won’t need a new supervisor, as we might be able to sort it out remotely. But we will both think about this.

Also discussed possible funding sources from August onwards, he said that he should be able to fund me for 3 to 6 months using some Lero grant money, but this would have some associated responsibilities. I asked whether I should try to apply to IRCSET for an extension, and said that yes I should, but for the time-being, I should just look into what the formal process is to do that. Also he suggested that come June, I should apply to the school for a demonstratorship, and that he is trying to build a pool of Lero money to top-up stipends to the current level (as the school one is less than the IRCSET one).

Finally discussed research, I said that I didn’t really have alot to talk about, so Paddy suggested that in a week’s time, I present a pitch to him about where I currently am in my research, and where I am going.

Met with Paddy to discuss funding and an idea of direction in PhD

Paddy said that if his EU grants get signed off, he will garauntee me another 1 year of funding from September, the only requirements will be a chunk of work which results in a ~30 page document – something to do with autonomous software patching.

Also spoke to him about the idea of Vector clocks and how we can use them for opportunisic networking – he wondered whether we could derive some utility for locations, perhaps based on duration spent at a location, number of nodes in that location etc. etc.

He said that perhaps a good paper would be on techniques for analysing locations for use with opportunistic networking.

Paddy said that he wants me to aim to submit to CfP on Social Based Routing in Mobile and Delay Tolerent Nets the deadline is in June, and split the time up until then into 6 week chunks, and for the first chunk, tell him what I will be doing – i.e. what problems I am solving, and for the whole time, what my goals are.

Also spoke about my idea for using the Dublin Bus network for research and profit – he mentioned a guy in trinity who has access to a load of transport data and also suggested I dig out an email address of someone important at Dublin bus, and send them a formal email about gettin information about the bus, and CC him (so it looks official).

He also mentioned the TextUS service based at DCU, (runs the Aircoach SMS payment service, and the SMS parking scheme) who we could collaborate with to provide a TFL type service for dublin.

Spent a few hours going over the following paper with Davide:

Kossinets, G., Kleinberg, J., & Watts, D. (2008). The structure of information pathways in a social communication network. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining – KDD ’08 (p. 435). New York, New York, USA: ACM Press. doi: 10.1145/1401890.1401945.

This was a very useful session, as it meant that we were forced to really understand the paper.

The authors present analysis of email datasets usin using vector clocks as a framework. They argue that the issues of out-of-date information and indirect paths are central to the understanding of the patterns of systemic communicatoion.

They explore Granovetter’s theory of weak ties, which basically says that long range connections can give better information than close connections.

This paper lead me to think that vector clocks would be a great way to discover the state of an unknown network from the point of view of each node. E.g. if a node exchanges vector clocks with other nodes it meets (perhaps with some probability, and time restriction) it could quicky build up in internal state of the following:

• the number of nodes in its connected network
• hops to other nodes (?? maybe ?? – )
• the range of other nodes (i.e. the amount information update a node gives about other nodes) – which can be used as a routing metric
• membership clustering using the ball of radius (i.e. the nodes it is up to date with to some value Τ days, which could be based on periodicity)
• periodic degree of a node can also be used (using T as the period)  as a routing metric

Each node must have a unique identity (perhaps based on BT Mac address), even Open World nodes that are not members of the closed world can be counted when it comes to degree calculations, but only as a ramp up, as only closed world nodes (i.e. others using this algorithm) will be of interest when sending messages.