Wireless project- virtual drums using sunspots
Finally now that my semester is over and I have loads of free time, i will start writing about our wireless project-Virtual Drums using SunSPOTs. It all started when I first entered the Wireless Fundamentals class after a short vacation in India. I had attended my other two classes (full of people I didn’t know) in the afternoon. I was expecting to have no luck in this class either. When i entered the class i was so relieved to see Vijay in class. Though I saw a few familiar faces but they were just acquaintances. Then Dinesh entered and I remembered all the days in CSE Services. Dinesh and Vijay shared most of the courses so they had decided to do the project together. I asked Vijay if i could join them and he said okay. I was quite relieved I must say. Then Dinesh told me Shrikanth would also join our team. We had seen the earlier semester projects and were anxious to start working on the SunSPOTs.
How to start? We created a google doc and decided to add our project ideas in that. We decided on a server monitoring project wherein we use different sensors to detect intrusion, follow it using camera and send the videos/photos back to the administrator. Dr. Liu wasn’t very happy with the concept and he said it too easy(we thought we were over ambitious). Then we sent him few project concepts and hold him to select one. One interesting concept which i thought had lot of application was the automatic traffic signal based on the number of vehicles approaching the intersection.
But Dr. Liu had already made his mind on another project. Vijay sent me a link about new type of instruments using hand gestures which helps kids create music. So how can we create music using SunSPOTs. Guitar too tough, piano not possible, Drums hmmm. Drums can be easy. So Shrikanth and Vijay started searching for projects on music using sunspots. They found an interesting site : JFugue
But we just wanted to play midi files of different parts of a drum set. May be we can different intensities also. Once we found a java class which played midi files and the sounds we were ready to start. But we were scared how we would manage to code these devices. I personally had no experience working on a sensor device. Thanks to the “SunSPOT quick start tutorial” in NetBeans we got everything set, deployed the BounceBall demo. This is what we did on day 1. We also decided to meet every Tuesdays and Thursday for an hour.
Day 2: “We created music”, says Vijay. See the videos below for the results of day 2.
Day 3: Next step was to add intensity to our drum set. Based on how fast you swing the SunSPOT, you get a given beat. Just two intensity levels for the time being. Watch the video below.
Then we hit a roadblock. We had tough time getting everything to work together. So we decided to ask Dr. Liu. He suggested having a sunspot for each Drum/Cymbal. Using the signal strength we decide the proximity of the SunSPOTs. Though this approach worked well, we wanted to make the project simple. As we kept adding to the complexity of the project , we knew we were increasing the chances of failure. So we decided to work with only a single base station to process the information from the other SunSPOTs and play the sound. So 2 SunSPOTS were used as sticks and one SunSPOT as the bass drum. For more information see the video below:
Now we were thinking of presenting our project in class. What better way to present than to play the drums on a song. So we had to find a song with simple drum beats. We used to go to an indian restaurant after our team meetings every tuesday and thursday. While going to the restaurant we used to listen to songs and try to figure out how tough it would be to play drum on them. While looking for songs with drums, we found a song with distinct congo beats. And the rest was history:
That went well. Okay back to our drum set. So to explain our drum set here is Shrikanth:
Okay so let me give you a brief demo of our final product before we go into our performance in class:
And finally the uncut version of our performance. I think it went well. At least nothing was thrown at us. Dr Liu was very happy and he also insisted on us exhibiting the project in the Engineering Week in Spring 09.
So finally I am at the end of this post. I will thank the few of you who read the entire post and watched all the videos. Thanks for all the support we got. I promise an awesome show in February. Engineering week here we come….
Okay i will be a little selfish and add one video of me enjoying the drums. If you need more information about this project mail me @ mayur.motgi@mavs.uta.edu.
Nah… No future as a drummer. See you soon.
SunSpot Reset Button Not Working…..
We recently had the problem with our SunSpots where in the SunSpots stopped responding, when we tried to update the firmware or deploy any code we got the following error:
“[java] [waiting for reset] Caught java.lang.IllegalArgumentException: negative sleep time while collecting/sending sensor sample.”
The main problem was the reset button was not working.
After lot of googling we didn’t find any answer. None of the users had ever encountered the error. We found a lot useful sites which help troubleshoot. One of them is given below:
http://sunspot-evrenbingol.blogspot.com/2008/11/resetting-button-does-not-work.html
https://www.sunspotworld.com/forums/viewtopic.php?f=25&t=564
We decided to try constantly resetting the SPOT by hitting the control button the moment the rapid green flashes stopped to see whether I could keep it in a semi-controlled state of crashing long enough to at least get code deployed. And it worked!!!!!! Though i don’t know how to rectify this problem, at least i can get the code deployed to the SunSPOT for our demo today.
I will write a post for our SunSpot project soon. We call our project “Virtual Drums”.
Max Flow and Min Cut
A common question about networks is “what is the maximum flow rate between a given node and some other node in the network”? For example, traffic engineers may want to know the maximum flow rate of vehicles from the downtown car park to the freeway on-ramp because this will influence their decisions on whether to widen the roadways. Another example might be the maximum number of simultaneous telephone calls between two cities via the various land-lines,satellites, and microwave towers operated by a telephone company.
An infinite flow rate is impossible because the individual roads or telephone links have limited capacities to carry flow. On the other hand, there are usually multiple ways to drive between the downtown car park and the freeway on-ramp, or to route calls between two cities. Finding the maximum flow involves looking at all of the possible routes of flow between the two end-points in question. When the system is mapped as a network, the arcs represent channels of flow with limited capacities. To find the maximum flow, assign flow to each arc in the network such that the total simultaneous flow between the two end-point nodes is as large as possible.
A further wrinkle is that the flow capacity on an arc might differ according to the direction. For example, a particular road might have two lanes in the A to B direction, but only one lane in the B to A direction. Or it might be simply a one-way street, with no flow in the B to A direction at all. In figure below, the labels on the arcs indicate the flow capacities in both directions. For example, the label near node A on the arc A-B indicates the flow capacity in the A-to-B direction, while the label near node B on the arc A-B indicates the flow capacity in the B-to-A direction.
figure 1.
Let’s imagine that the flows in figure above are in units of vehicles per minute. Here are some examples of routes on which flow could travel from node A to node G:
• 4 vehicles per minute along the route A-D-E-G. This is the maximum flow on this route because of the bottleneck on arc D-E.
• 3 vehicles per minute along the route A-B-E-G. The bottleneck here is the arc B-E.
Note, though, that with the simultaneous flow on route A-D-E-G, the total flow on arc E-G is now 7 vehicles per minute.
• 4 vehicles per minute along the route A-C-F-G. The bottleneck on this route is arc A-C.
This set of flows gives a total flow of 4 + 3 + 4 = 11 vehicles per minute from A to G. But it is not themaximum flow attainable from A to G. There remain unused routes for carrying flow between the two end nodes. We need an organized method of tabulating the routes and flows, and this is provided by the Ford and Fulkerson method. As we will see later, the maximum flow problem can be solved by linear programming, but the Ford and Fulkerson method is simple and even faster than linear programming when implemented on a computer. Ford and Fulkerson first published their method in the Canadian Journal of Mathematics in 1956 – it is a real classic paper, very often referenced to this day.
The main idea is careful bookkeeping of the flows assigned to different routes from the origin node to the destination node. The steps in the method are:
1. Find any path from the origin node to the destination node that has a strictly positive flow capacity remaining. If there are no more such paths, exit.
2. Determine f, the maximum flow along this path, which will be equal to the smallest flow capacity on any arc in the path (the bottleneck arc).
3. Subtract f from the remaining flow capacity in the forward direction for each arc in the path. Add f to the remaining flow capacity in the backwards direction for each arc in the path.
4. Go to Step 1.
On termination, the sum of the flows along the paths found during Step 1 gives the maximum total flow between the origin and destination nodes.
Let’s try the Ford and Fulkerson method on the network in figure above. The results are shown in Figures 1 through 6. Figures 2 through 4 show the three flow paths suggested earlier, and Figures 5 and 6 show two more flow paths that can be added before we are unable to find a path that can support a strictly positive flow f. Note the bookkeeping on the flow capacities as the solution progresses, and how it becomes more and more difficult to find a path having positive flow capacity.
The algorithm terminates after the last path is found in Figure 6. No more strictly positive flow paths can be found between A and G. This is obvious since all paths must pass through the set of arcs B-E, D-E, F-E, and F-G, and these arcs have all had their flow capacities in the forward direction reduced to zero.
Figure 2.
Figure 3.
Figure 4.
Figure 5.When the algorithm terminates, the maximum total simultaneous flow of vehicles from A to G is given by summing the flows on the 5 paths we selected: 4 + 3 + 4 + 2 + 1 = 14 vehicles per minute.
But what is the actual pattern of flows that gives this optimum? How much flow should go on each arc, and in which direction? This is found by looking at the difference between the initial flow capacity and the final flow capacity: a positive difference indicates a flow in the associated
Figure 6.
direction (a negative difference is ignored). The pattern of flows – and their directions – which gives the maximum simultaneous flow of vehicles per minute, is shown in Figure 7. The arc labels in Figure 7 show the amount of flow in each arc. Note that the principle of flow conservation at a node is respected. For example, the flows entering node F total 7 vehicles per minute, as do the flows leaving node F.
You probably noticed that it becomes harder and harder to find a strictly positive flow path as the algorithm progresses and all the easy-to-spot paths are used up. You might think this would be a
Figure 7.
problem in a computer implementation of the method, but it turns out that simple depth-first and breadth-first searches are quite efficient for finding positive flow paths.
One way to find the minimum cut is to simply try all possible cuts and select the smallest. However the number of possible cuts is extremely large, and it is impossible to enumerate all possible cuts in a larger network, even with extremely fast computers and a lot of computing time.
A better approach is to make use of the max-flow / min-cut theorem: for any network having a single origin node and a single destination node, the maximum possible flow from origin to destination equals the minimum cut value for all cuts in the network.
This may seem surprising at first, but makes sense when you consider that the maximum flow through a series of linked pipes equals the maximum flow in the smallest pipe in the series, i.e. the flow is limited by the bottleneck pipe. The minimum cut is just
Figure 8.a kind of distributed bottleneck; i.e. a bottleneck for a whole network as opposed to a simple bottleneck for a series of pipes.
The max-flow / min-cut theorem means that we can determine the minimum cut value using the Ford and Fulkerson maximum flow algorithm. But the real question is where the minimum cut is located. If our traffic engineers determine that the maximum flow rate of vehicles from the car park to the freeway on-ramp of 14 vehicles per minute is too small to handle peak rush hour traffic, then we are going to want to expand the roadways. But which ones? There is no point in expanding roadways that are carrying less than their maximum capacity. The only roadways to expand are those that are part of the bottleneck, i.e. the minimum cut.
The minimum cut is actually simple to find after the Ford and Fulkerson algorithm has been completed. Simply mark the arcs that are carrying a flow equal to their maximum flow capacity and look for a cut that consists only of marked arcs and no other arcs. It often happens that not all of the marked arcs are used in the cut, and it may also happen that thereare multiple cuts that can be made in this way. The results for our vehicle flow example are shown in Figure 9. Not surprisingly, the cut is the same set of arcs whose flow capacities were forced to zero by the Ford and Fulkerson algorithm, hence forcing the termination: B-E, D-E, F-E, and F-G. The cut value in the forward (origin-to-destination) direction is 14 for these arcs, the same as the maximum flow. These four arcs are the bottleneck for the network. These are the roads that the traffic engineers should consider widening to increase the flow from the car park to the freeway on-ramp.
Keep in mind, though, that you may not get one unit of increase in the maximum flow for every unit of added capacity in an arc from the minimum cut. This is because the increased flow through that arc may cause another bottleneck to come into play upstream or downstream from that arc.
Figure 9.