They Did Not Do So In Vain

David Ding

December 5, 2020

Once upon a time, when we can travel freely around the world, I garnered a complimentary trip to Ireland, courtesy of University of Toronto. I was in my final year of college, completing my undergraduate studies, when I stumbled upon an essay competition hosted by the Undergraduate Awards programme based in Ireland, way back in 2014. (It has been six years?!). I was rather intrigued, so I went to their website and dived deeper:

Innovation, collaboration, impartiality and inclusiveness--How unbelievably significant those words would apply to our society just six years later. In a tumultuous 2020, we saw events that challenged even our basic rights to breathe, whether through an almost invisible enemy permeating through the air and into our lungs or an actual invisible enemy, systematic racism, pent-up in times past and released tragically this year in forms of police brutality and social injustice. Yet, miraculously, I sense a light at the end of all this chaos and disorder, and that feeling is prompted by none other than those four words. Facing a daunting pandemic, I saw institutions around the world rose to the challenge of not only developing vaccines, but ever-improving the logistics of treating and mitigating the effects of Covid-19 and flattening the curve. Innovation and collaboration went off the charts in the medical industry, while at the same time everyone came together, put differences aside, and showed empathy in lifting communities ravaged by the Coronavirus. Impartiality and inclusiveness amplified their desperate calls of unity when the death of George Floyd broke the last proverbial straw and millions answered back. Say their names: Breonna Taylor, Ahmaud Arbery, and countless other African Americans senselessly killed at the hands of police brutality, racism, and prejudice, somehow brushed aside in the past by our guilty afflictions of focusing on trivial affairs, finally received a chance this year to even begin the long road to justice. Facing the daunting challenge of battling systematic racism, everyone came together again, fueled by impartiality, inclusiveness, and a desired for a more just society. Black Lives Matter. So yes, there will be light at the end of the tunnel, at least the way I sense it.

Anyways, this post is not about the present, but about the past--six years ago, after browsing the Undergraduate Awards programme, I entered their essay competition. The programme accepts undergraduate works of all areas (mine was under "Engineering & Mechanical Sciences"), and the bar to even enter the competition was that the work must have been graded, and the grade must be an A-equivalent. Fortunately, my senior-year thesis project just scraped an A, and hey, I'm eligible, by a hair, so why not give it a shot? So I edited my thesis to fit a conference style paper, and hit "submit".

I didn't really pay attention, at least at the time when I submitted my work back in May of 2014, about the judging criteria. I had low hopes because it was a global competition and I don't think my entry would hold up against the competition around the world. Then in September that year I opened my Email one day...

		
Mon, 8 Sept 2014, 12:45
to davidy.ding

Dear David,

Congratulations! Your essay, 'Throughput Analysis of Cognitive Radio-Based Small Cells in LTE Downlink Networks', has been Highly Commended in the Engineering & Mechanical Sciences category of The Undergraduate Awards 2014.

This means your essay rates in the top 10% of submissions to this year’s programme, which received 4,792 submissions from undergraduate students around the world.
 
As a Highly Commended entrant, you are invited to the UA Global Summit (link), which will bring together Winners and Highly Commended entrants from all over the world to Dublin, Ireland on November 19-21, 2014. You’ll get to meet your international peers as well as our amazing list of speakers.		 

A limited number of tickets are available exclusively for Highly Commended entrants to purchase, which you can do personally or through your university. Tickets are allocated on a first-come-first-served basis, so if you are interested in attending, let me know and I’ll send on more details.

Also, watch out for our announcement of the 2014 Winners later this month. As you have been Highly Commended, you’re in the running to be named a Winner!

Congratulations once again. Being Highly Commended is a fantastic achievement, and I hope to see you in Dublin in November.


Kind regards,
		

Um...someone punch me? To say that I could not keep myself steady while reading what I just received would be a colossal understatement. I immediately forwarded this to my then thesis supervisor, Prof. Ravi Adve, who also congratulated me on the achievement. One of the prizes for just being shortlisted was the chance to attend the UA Global Summit later in November of that year, which sounded very exciting. Again I clicked into the link provided to browse that year's programme, and oh boy it was a doozy. The lineup of speakers included former United Nations Legal Counsel Patricia O'Brien and Nobel Peace Prize laureate Mairead Corrigan Maguire, just to name a few. Unfortunately, at the time my family was just scraping by financially, so I could only wish those that decided to go best of luck and hope that they would obtain something out of it. Then, two weeks later...

Tue, 23 Sept 2014, 10:07
to davidy.ding

Hello David,

Congratulations on your standing in the 2014 Undergraduate Awards. As a Highly Commended candidate you are invited to attend the summit to present your paper. I am very pleased to inform you that, if you choose to attend the summit, the cost of your ticket will be covered by the University of Toronto.

Please contact me by September 26th if you wish to attend and I will arrange for the purchase of your ticket.

Looking forward to hearing from you,

Manager, University Awards
Enrolment Services

Toronto, Ontario
		

Wow, what could I have said except for that I was proud to have spent both my undergraduate and my graduate studies in entirety at the University of Toronto. (Yes there was an article about it too from the university). Anyways, on a cold November morning in Toronto, my mom dropped me off at the airport and onwards to Ireland I go!

***

The journey began when I contacted Prof. Adve who was teaching my digital signal processing class during my senior year. It's a funny thing, but I feel what I did back then had a lot in common with the world we live in today and what I had the opportunity to experience during that eventful week in November of 2014.

My undergraduate research was on Cognitive Radios. I don't know whether this technology is still on the cutting edge today, but in 2014, when all the hype was surrounding 5G, it was big news. Cognitive Radios are small transmitting nodes in wireless communication networks that are typically placed near the edge of cells to improve cellular coverage. Such configuration is known as Heterogeneous Networks which were the backbone of my graduate research that I talked in length in my 5G blog post. The entire motivation behind Cognitive Radios lies in the fact that wireless spectrum is an expensive commodity. There is only so much "air space" that one can communicate using electromagnetic waves before the laws of physics render such actions downright impossible. (Later there are technologies such as mm-waves that aim to expand the usable frequency, but I digress.) Cognitive Radio exploit the fact that the big, bad wolf, aka regular base stations, don't transmit signals ALL the time. I hate to call Cognitive Radios vultures, but they essentially act that way by listening in on the same transmitting spectrums as those of regular base stations, and whenever there is a spectrum "hole" opening up in a resource block, be it in the temporal or in the frequency dimension, cognitive radios jump in and use it to do its transmission, before quickly returning to silence for the base stations to do their thing.

The hard part, of course, would be actually detecting that the spectrum is free. Cognitive Radios detect whether the spectrum is free or not by taking samples of the air space and measuring the received energy of electromagnetic waves, if any. The problem is that even if the spectrum is truly free of any base station activities, the measured energy still won't be zero because of background noise (technical term: Additive White Gaussian Noise). Each cognitive radio takes \(m\) samples, averages them, and then transmit the results to a decision desk called the "Fusion Center (FC)". Here I assume there is a narrow, dedicated channel for Cognitive Radios to send in the results. If there are \(N\) radios, and FC makes a decision to use the channel if at least \(k\) out of the \(N\) radios detect that the channel is free, we would say that the FC is using a "k-out-of-N rule". Special cases of \(k\) are given below:

• \(k = 1\): "Or-rule"; one green light is good enough for the FC.
• \(k = \lceil\frac{N}{2}\rceil\): "Majority Rule"; needs at least half of good to go reports by the Cognitive Radios for the FC to give the okay signal.
• \(k = N\): "And-rule"; the decision to transmit on the channel must be unanimous.

Therefore, for each cognitive radio, there would be an energy threshold that would be pre-determined. If the average detected energy is below that threshold, and FC, after receiving all of the reports and makes a decision based on some "k-out-of-N" rule, would then decide whether that channel, at that time, can be used. The decision is very important, as a wrong one either robs of valuable resources for Cognitive Radios to provide coverage to cell-edge users or adds interference to transmitting base stations and thereby lowering the quality of service for those users talking to those base stations. When we have limited wireless spectrum, it's a tough world out there.

The aim of my research, therefore, would be to come up with an optimal energy threshold that all Cognitive Radios in the network can use to ensure the best of both worlds. The threshold is intrinsically tied to the probabilityof "false alarm", or the chance that those radios are either too conservative in making the call about the state of the channel or not enough. The trade-off considered here is very important. If the false alarm probability is too high, then it means the Cognitive Radios are too conservative in their decisions and we would hit a lot of false alarms: free channels that the radios won't be using. This lowers the rate of cell-edge users. On the other hand, if the false-alarm probability is too low, then the Cognitive Radios would be all too eager to use their channels, at the expense of base stations that could potentially be using it at the same time, thereby lowering the rate of those users.

My research is peculiar in that it has a theoretical element and a heuristic one working together to achieve the goal. The theoretical element calculates the probability of false-alarm based on a given energy threshold and uses that probability as a key parameter in the network model. The calculations are based on the theories and concepts in statistics. Then, the heuristic part kicks in and simulates (via Matlab), the throughput, or the rate of both edge-cell users with the given probabilities of false alarms. As mentioned before regarding the trade-off, as we increase the probability of false alarm, we make the cognitive radios more and more conservative in their decision-making, thereby lowering the throughput of cell-edge users. At the same time, as the probability of false alarm approaches zero, the radios are more prone to say "okay" to using the channel and we would see a degradation of those users taking to the base stations, which are the primary users of the channel. The simulations are a heuristic way of solving this tricky optimization problem to find a common ground for both the primary users (base stations) and the second users (cognitive radios) residing in the same spectrum.

***

Finding common ground. Such concepts that seemed so otherworldly mundane appear all but forgotten in today's messy scene of international diplomacy. However, back in 2014 at the UA Summit, I had an unforgettable experience during the dinner reception (mind you, I slept only 2 hours in the 12+ hour journey from Toronto to Dublin, with three connecting flights) that has etched into my memory forever. I met Ms. Mairead Corrigan Maguire, 1976 Nobel Peace Prize Laureate. She was courageous and instrumental in ending the deep ethnical and political conflict between Northern Ireland and Britain. The deep divide between the islands of Ireland and that of Great Britain spans a millennium, with militia forces on both sides fighting incessantly to this day. One such skirmish ended in tragedy for Ms. Maguire, when her sister, Anne, was run over by an Irish militant. Instead of feeling resentful towards the Irish, Maguire instead organized march of 35000 people in Belfast, with Protestants and Catholics joining forces together to use the most power weapon for change--peaceful protests, to respond to the situation. She believed that most effective way to end violence was not through violence, but through education. I was so touched when I learned of this. Not only was she promoting peaceful protesting to get a hopeful message across, but she also stressed education as a way to change for the better. It was the same sentiment that I carried today as a seed for starting my blog in this eventful year.

When I met her, I meekly introduced myself. I was amazed that she was interested in my background, and although I did not focus my studies on international affairs, I spoked from my heart and express my utopian vision of a world living in peace, as John Lennon had aspired, and even dared to suggest a way for countries to start trusting each other more.

"Trust." She repeated.

***

The first step in determining the optimal energy threshold value would be to see which rule works best for the FC in deciding on behalf of all of the Cognitive Radios. The step before that would actually be to use statistical theory to determine the probability of false alarm for each Cognitive Radio given a threshold \(\theta\). Denoting such probability as \(p_f\), we have: \begin{equation} p_f = P(\epsilon > \theta | H_0) \end{equation} The above is just a fancy way of saying the probability of false alarm at each Cognitive Radio is the probability that the average detected energy value exceeds the given threshold, under the null hypothesis \(H_0\) that the channel is actually free. Assume we have \(N\) Cognitive Radios, and the FC is using the "k-out-of-N" rule, for some given value of \(k\), the probability of false alarm at the FC, denoted as \(p\), is given as what?

Well let's think about it. Given that the channel is free, the only source of energy would be the background noise, which, although it is random, does have the same statistics everywhere in that it is normally distributed with mean of 0 and variance of \(\sigma^2\), latter being the power density of the background noise. So that means all of the \(N\) Cognitive Radios would have the same \(p_f\)! Let the random variable \(X\) denote the number of Cognitive Radios making a false-alarm detection. (i.e. the channel is free yet the said Cognitive Radios reported base station activity), how would \(X\) be distributed? The answer is a binomial distribution since each Cognitive Radio independently makes decisions with probability of false alarm being the same \(p_f\). Specifically, \begin{equation} p = P(X \ge k) = 1 - F_X(k-1; N, p_f) \end{equation} Where \(F_X\) is the binomial CDF of \(X\) with parameters \(N\) and \(p_f\), the probability of false alarm at each Cognitive Radio. If at least \(k\) radios report, falsely, that the channel is currently in use, then FC, using the "k-out-of-N" rule explained earlier, would not be using it.

Tying the threshold \(\theta\) to \(p\) would get a bit technical and I feel would not be interest to most readers. However, for completeness, I will write it down. Bonus marks if you can derive it: \begin{equation} \theta = \frac{\sigma^2 \times Q^{-1}(m, p_f)}{m} \end{equation} Where \begin{equation} p_f = \frac{\log\left(\frac{1 - p}{\binom{N}{k-1}(N-k+1)}\right)}{\log\left(\frac{k - 1}{N-k+1}\right)} \end{equation} Here as reminder: each Cognitive Radio takes \(m\) samples of energy and compares the average against the threshold. The function \(Q^{-1}(m, x)\) is the inverse complementary CDF of the chi-squared distribution with \(2m\) degrees of freedom.

What we have done here is that we have tied, mathematically, the threshold \(\theta\) to the probability of false alarm at the FC, \(p\). Doing so would simplify things a lot as we would only need to focus on \(p\) in our simulations. Once we have the optimal \(p\), equivalently speaking, we would have our optimal \(\theta\). The only parameter left is \(k\) for the FC to implement a decision rule. This is done by looking at various rules aforementioned: or-rule, and-ruld, and of course, majority rule, and picking out the best one:

The above chart graphs \(p\) against normalized \(\theta\) for the given parameters and the three rules. This chart provides a visual representation of how the two variables are connected, and how once we have the optimal \(p\), we obtain our desired \(\theta\). Furthermore, the scatter points are simulations of the theoretical curve, for sanity checking. It turned out that the math was pretty solid. Who knew?

Long story short, after further analysis which I feel would be too esoteric to describe to the readers, in the end the "Majority Rule" was the best among the three rules considered, so I chose that for the FC going forward into the second part of my research--throughput simulations!

***

Back in 2015, I saw a movie where the protagonist stated, "If you solve enough math problems, you get to go home." The speaker, of course, was NASA Astronaut Mark Watney, portrayed by Matt Damon, and the movie was "The Martian". (Incidentally Matt Damon also got to solve a lot of math problems in Good Will Hunting 18 years prior, but I digress). When I watched that film, I couldn't help but recall the conversation I had with Dr. Joseph Roche, astrophysicist, educator, and professor teaching at Trinity College Dublin. During the UA Summit, what moved me for Dr. Roche was his decision to join the Mars One mission that aims to establish the first human settlement on Mars in 2024. What's extraordinary about the people participating in this mission is that this is a one-way ticket to the Red Planet. Yes, once you've embarked on this journey, you will never set foot on Earth again. The best chance you have would be to make it to Mars safely. I don't think I can bring myself to join this mission, and I would probably be correct assuming most of you the same way as well. Yet, Dr. Roche signed up for it. When I asked about his motivation, he said: "Humans are meant to push for the unknown." He didn't do it to gain fame, but rather for the good of the human race. I will never forget the conversation I had with him. Reflecting on what he said, in the grand scheme of the Human Dream, every conflict or disagreements we have with each other on this planet, be it out of our politics, or unfortunately our skin colors, seem so inane.

***

My undergraduate thesis was also about solving a problem. Specifically, this one: \begin{align} & \underset{p}{\max} & & \sum_{i = 1}^R \sum_{l = 1}^{N} \log_2 \left(1 + \frac{g_iP_{SU, l,i}}{\sigma^2 + I_{PU,i} + \sum_{j \neq l}^{N} I_{SU,j,i}}\right) \\ & \text{subject to} & & \sum_{i = 1}^R \log_2 \left(1 + \frac{g_iP_{PU,i}}{\sigma^2 + \sum_{l = 1}^{N}I_{SU,l,i}}\right) \ge R_{\text{acceptable}}\\ &&& 0 \le p \le 1 \end{align}

In order to understand the above problem, and how I can solve it heuristically, I will illustrate the network model:

Here I am assuming a downlink, outdoor heterogeneous cellular network, with a cell reuse factor of 3. Within a set of three cells, there will be \(R\) resource blocks for which there are \(N\) Cognitive Radios that will scan and report results to the FC. The base station are considered Primary Users (PUs) because they have the right-of-way of using any resource block. Cognitive Radios, being opportunistic, are considered Secondary Users (SUs). They are not allowed to use the channel if it is occupied by a base station. Here I am assuming several things. For simplicity of scheduling, I am assuming each resource block can be occupied by at most one base station. Of course, multiple Cognitive Radios can use a resource block, and when that happens, each Cognitive Radio on that channel gets equal fractions of the resources if they can be used. We are only considering temporal holes here, so each resource block is really one coherent time frame for downlink transmission. In addition, we are assuming that the user association and transmit powers of each base station/Cognitive Radio are fixed (in my graduate research, I delved deeper into the problem when those factors can in fact be optimized).

The path loss models dictating the signal propagation in the outdoor environment were taken from literature, and the distances were given in the diagram above. I randomly scattered users across the network within the cell coverage zones of the Cognitive Radios, and please note that some of the users will be associated with a nearby base station. This was possible since base stations transmit with much stronger powers than its Cognitive Radio counterpart. The only advantage Cognitive Radios have over base stations is the location--the former is placed near cell edges to provide additional coverage as they would be closer to the users than base stations.

The decision rule at the FC is the Majority Rule, as aforementioned, meaning that \(k = \lceil\frac{N}{2}\rceil\). Furthermore, \(P\) is the received power of base stations/Cognitive Radios, as denoted by the corresponding subscripts in the problem statement. Similarly, \(I\) would be the interference power. This value is the dependent variable for the different values of \(p\), which is the probability of false alarm at the FC. Finally, \(\sigma^2\) is the average power of the background noise.

The problem states that I seek to maximize the sum rate of the Cognitive Radio network, as shown in the objective function where each individual rate of Cognitive Radio \(l\), if the radio is transmitting in resource block \(i\), is given by the Shannon-Equation, which I talked about in my 5G post, as below: \begin{align} C_{l,i} &= \log_2(1 + \text{Signal-to-Noise-plus-Interference-Ratio}_{l,i}) \\ &= \log_2 \left(1 + \frac{g_iP_{SU, l,i}}{\sigma^2 + I_{PU,i} + \sum_{j \neq l}^{N} I_{SU,j,i}}\right) \end{align} (Note that the factor of 1/2 at the front is gone because we are talking about the passband in wireless communication networks.)

The above expression can be cranked all the way up, if the probability of false alarm is sufficiently low and Cognitive Radios transmit at will. However, this will degrade the quality of service for the base station users, which is mentioned in the constraint: \begin{equation} \sum_{i = 1}^R \log_2 \left(1 + \frac{g_iP_{PU,i}}{\sigma^2 + \sum_{l = 1}^{N}I_{SU,l,i}}\right) \ge R_{\text{acceptable}} \end{equation} So given any acceptable rate, we can start with a very high probability of false alarm to satisfy the constraint, and then slowly decrease it to improve the Cognitive Radio users' sum rate, until the constraint is about to be violated.

Solving the above problem mathematically is very hard, so that's where simulations come in. Given all the system parameters, I determined heuristically the rates of both primary and secondary users, as a function of \(p\), such that we can see what the two worlds look like and find a compromise in between.

***

Ireland is a world in itself. The urban side exudes an aura of livelihood with its 18th century style houses and buildings watching over the bustling cars and double-decked buses roaming about in the street as a new dawn awakens. Yet, like Dr. Jekyll and Mr. Hyde, things turn fast in rural Ireland. Trees stand in the still November chill, falling victim to the fog that casts a spell slowly turning those in the distance into ghostly silhouettes while horses graze the dewy fields about. It was quite a sight to behold.

The Christ Church Cathedral, founded in 1030, was the site of the closing ceremonies of the UA Summit 2014. What was neat about the Cathedral is that it has a crypt, which, while sounds scary, hosted the reception afterwards. Before coming to the summit, the winners of each category were announced, and while I did not win in the end, I was very happy for the winner and we had a blast at the closing ceremony. Former United Nations Legal Counsel Patricia O'Brien delivered the closing remarks and presented the awards. The night before we parted the following day, she urged us to grow from this experience, using our areas of expertise to work together to solve problems of the future.

***

The problem at hand, though, is still unsolved: base stations which are the primary users do not wish Cognitive Radios to abuse their opportunistic presence. Yet, the cell-edge users who are looking forward to having better coverage are banking on the radios to start transmitting signals whenever possible. The dial controlling all this is the probability of false alarm at the decision desk, the FC. There is only one way to solve this. Let's see the throughput simulation results!

As expected, when probability of false alarm is increased, the throughput for Cognitive Radios decreased. This is reversed for base stations. Of course, the curves are not perfectly smooth because we are talking about simulations, and there are a lot of randomness in the process, but it's good to see that the trend matches with intuition. Here, we see that the rate of base stations being the primary users doesn't start to pick up unless \(p\) is greater than 0.04, while the rate of Cognitive Radios, being the secondary users, begins to dip precipitously once \(p\) starts to grow from 0. This means that, if we say let \(R_{\text{acceptable}}\) to be around 6 bits/s/Hz for the base station network, then our optimal \(p\) for the 90% spectral occupancy case would be around 0.02 thereby giving the Cognitive Radio network a throughput of around 130 bits/s/Hz (the latter had a higher sum rate because there is only 1 base station per resource block in my model). Extrapolating this value for our energy threshold, and we obtain the optimal normalized value of \(\theta = 1.6\). This means for the 90% spectral occupancy case, the threshold should be set to 1.6 times the average power of the background noise.

***

Resolving a dispute between two tiers of communication nodes in a wireless network over a precious commodity led me to an experience where I learned of others resolving much bigger disputes over much rarer resources. I was amazed at the talent and the energy exuded by my peers at the conference, and I will be forever proud to have associated myself with an organization that championed those things, along with inclusiveness and impartiality. Now I want to show my readers, out of all the photos I've taken during this unforgettable trip, my favorite, by far:

The three peers standing next to me each came from a different continent: Asia, Europe, and Africa. With me being from Toronto, that makes the four of us, literally, coming from the four corners of this planet to meet at the UA Summit 2014. If there are still people who weren't convinced, we are of the same race--the human race. And when we put our differences aside and realizing that we are all striving for the same dream, the Human Dream, we can achieve the greatest of things. People who preceded us resolved decades long conflicts and educated and paved a way for future generations to reach for the stars. Now it's up to us to continue the work, be it helping our communities, defeating a pandemic, or strive for a more just society. We will show those that came before and sought to educate us that they did not do so in vain.